592. Two City Scheduling
A company is flying 2n candidates to onsite interviews, split across two offices: exactly n people must go to city A and exactly n to city B. Flying person i to city A costs costs[i][0] and flying the same person to city B costs costs[i][1].
Your function receives the array costs — one [aCost, bCost] pair per person; the number of people is always even — and must return a single integer: the minimum total airfare that puts exactly half the group in each city.
The tension: some people are cheap for either city, and picking them for A may waste their even cheaper B fare. Think about what choosing A over B costs relative to the alternative, not in absolute terms.
Example 1:
Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: Send persons 0 and 1 to city A (10 + 30) and persons 2 and 3 to city B (50 + 20). Total 110. Person 1 must not go to B — the 200 fare is the trap this example sets.
Example 2:
Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859
Explanation: The best split sends persons 0, 3 and 5 to city A (259 + 184 + 577 = 1020) and persons 1, 2 and 4 to city B (54 + 667 + 118 = 839), for 1859 total.
Constraints:
- 2 ≤ costs.length ≤ 100
- costs.length is even
- 1 ≤ costs[i][0], costs[i][1] ≤ 1000
Hints:
Imagine everyone flies to city B first. Moving one person to city A changes the bill by costs[i][0] − costs[i][1] — a signed "switch price" that can be negative.
You must move exactly n people. To minimize the total, move the n people with the smallest switch prices: sort by costs[i][0] − costs[i][1], send the first half to A and the rest to B.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Expected output: 110