Description
A company is planning to interview 2n people. Given costs, an integer array where costs[i] = [aCostᵢ, bCostᵢ] is the cost of flying the iᵗʰ person to city A and city B respectively, return the minimum cost to fly every person to a city such that exactly n people arrive in each city.
Examples
Input:
costs = [[10,20],[30,200],[400,50],[30,20]]Output:
110Explanation:
Sort by aCost - bCost ascending: [[30,200],[10,20],[30,20],[400,50]]. Send the first 2 to city A (30 + 10 = 40) and the last 2 to city B (20 + 50 = 70). Total = 110.
Input:
costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]Output:
1859Explanation:
Greedy: sort by aCost - bCost ascending, send first n people to A, rest to B.
Input:
costs = [[10,10],[20,20]]Output:
30Explanation:
Any split gives 10 + 20 = 30.
Input:
costs = [[1,100],[100,1]]Output:
2Explanation:
Send person 0 to A (cost 1) and person 1 to B (cost 1); total = 2.
Constraints
- •
2 * n == costs.length - •
2 ≤ costs.length ≤ 100 - •
costs.length is even - •
1 ≤ aCostᵢ, bCostᵢ ≤ 1000