Community Problem
Two City Scheduling
Difficulty: Medium
Send exactly half the candidates to city A and half to city B at minimum total cost.
Two City Scheduling
Send exactly half the candidates to city A and half to city B at minimum total cost.
By @zarakamau
April 4, 2026
·
Updated May 18, 2026
672 views
14
4.3 (12)
I had a lead at Stripe describe this as their favorite "is the candidate going to over-engineer this with DP" filter. The DP solution is O(n^2); the greedy is one sort and a sum. The slick observation is that the cost of sending person i to city A versus city B differs by costs[i][0] - costs[i][1], and sorting by THAT delta tells you exactly which half goes where. The catalog covers Greedy basics but skipped this O(n log n) gem.
Two City Scheduling
A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the i-th person to city A is aCosti, and the cost of flying the i-th person to city B is bCosti.
Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.
Examples
Example 1:
- Input:
costs = [[10, 20], [30, 200], [400, 50], [30, 20]] - Output:
110 - Explanation: Send person 0 to city A (cost 10), person 1 to city A (cost 30), person 2 to city B (cost 50), person 3 to city B (cost 20). Total
10 + 30 + 50 + 20 = 110.
Example 2:
- Input:
costs = [[259, 770], [448, 54], [926, 667], [184, 139], [840, 118], [577, 469]] - Output:
1859 - Explanation: One optimal split: send the three with the smallest
a - bto A, the rest to B.
Example 3:
- Input:
costs = [[515, 563], [451, 713], [537, 709], [343, 819], [855, 779], [457, 60], [650, 359], [631, 42]] - Output:
3086 - Explanation: The greedy still resolves it cleanly with one sort.
Example 4:
- Input:
costs = [[1, 2], [2, 1]] - Output:
2 - Explanation: Send each person to their cheaper city. Total
1 + 1 = 2.
Constraints
2 * n == costs.length.2 <= costs.length <= 100.costs.lengthis even.1 <= aCosti, bCosti <= 1000.
Follow-up
Why does sorting by aCost - bCost work? Sketch: the total cost when sending person i to A is aCost[i] + sum_of_other_b, and to B is bCost[i] + sum_of_other_a. The DELTA is aCost[i] - bCost[i]. Lining up these deltas, the smallest n go to A (largest savings to send them to A), the largest n go to B.
Solution
Hints
Solution Walkthrough
Approach: Sort by Cost Differential (O(n log n) time, O(1) extra space)
If we hypothetically sent EVERY person to city B, the total would be sum(bCost). Now consider "upgrading" person i to city A: the cost changes by aCost[i] - bCost[i]. Some of these deltas are negative (cheaper to fly to A) and some positive (more expensive to fly to A).
We must upgrade exactly n people. The optimal choice: upgrade the n people with the SMALLEST (most negative, then least positive) deltas. Equivalently, sort by aCost - bCost ascending and send the first n to A.
Algorithm
- Sort
costsascending byaCost - bCost. - Let
n = costs.length / 2. - Sum: for
i < n, addcosts[i][0](A); else addcosts[i][1](B). - Return the sum.
Why It Works
This is the classic "choose the cheapest k from a list" greedy. Define delta[i] = aCost[i] - bCost[i]. Total cost as a function of which n we send to A is
Total = sum(b) + sum_{i in A} delta[i]sum(b) is a constant, so minimizing Total means minimizing sum_{i in A} delta[i] over all size-n subsets. The minimum is achieved by picking the n smallest deltas. Sorting by delta ascending and taking the prefix is the cleanest way to do that.
Complexity
Sample: costs = [[10, 20], [30, 200], [400, 50], [30, 20]]
Delta (a - b):
[10, 20]: -10
[30, 200]: -170
[400, 50]: 350
[30, 20]: 10
Sorted by delta: [30, 200], [10, 20], [30, 20], [400, 50]
First 2 go to A: cost = 30 + 10 = 40
Last 2 go to B: cost = 20 + 50 = 70
Total = 110Metric Value
Time O(n log n) for the sort
Space O(1) extra (or O(n) if you avoid mutating the input)Pitfalls
- DP overkill. The 2D DP
dp[i][a](firstipeople,aalready in A) is correct in O(n^2), but on a 100-person input it is wasteful. The greedy lands in 5 lines. - Mutating the input. The sort is destructive on the original array. Slice first if you need to keep the input intact.
- Misreading the cost columns.
costs[i][0]is the A cost;costs[i][1]is the B cost. Reversing them silently produces the COMPLEMENT of the optimal answer (sending the wrong half to each city).
Solution Code