Two City Scheduling
Medium · Greedy · Array · Greedy · Sorting
Problem
A company is flying 2n people to interviews. Sending person i to city A costs costs[i][0], and sending them to city B costs costs[i][1].
Exactly n people must go to each city. Return the minimum total flight cost.
Examples
Input: costs = [[5,40],[30,10],[20,25],[60,15]] Output: 50
Persons 0 and 2 fly to A (5 + 20), persons 1 and 3 to B (10 + 15).
Input: costs = [[1,100],[2,3]] Output: 4
Person 0 to A for 1 and person 1 to B for 3.
Input: costs = [[10,20],[30,200],[400,50],[30,20]] Output: 110
Person 0 is cheapest in A, but person 1 saves far more there (170 against 10). A: 10 + 30, B: 50 + 20, total 110.
Constraints
- 2 <= len(costs) <= 100
- len(costs) is even
- 1 <= costs[i][0], costs[i][1] <= 1000
Approaches
- Baseline: table over people and seats in A — time O(n²), space O(n)
Follow-up
The greedy works because the split is fixed at n and n, so only the difference a - b matters. The use cases loosen the split: seat limits on each office, and exactly k of m workers on one shift.
Related problems
Start free on Cariara · Coding problems · System design studio
