Two City Scheduling
Asked at Bloomberg
Problem
Two City Scheduling gives you 2n people with the cost of flying each to city A or city B, and asks for the minimum total cost if exactly n people go to each city. The greedy insight — sort by how much cheaper A is than B — is the whole problem.
Asked At
| Company | Difficulty | |
|---|---|---|
| Bloomberg | Medium | View all Bloomberg questions → |
How to Think About It
Sending everyone to their cheaper city ignores the constraint that each city gets exactly n people.
Key insight: imagine first sending everyone to city B. Moving person i to city A changes the total by costA - costB. You must move exactly n people, so move the n with the most negative (or least positive) difference.
So sort people by costA - costB ascending. The first n go to A, the rest go to B.
Walkthrough for [[10,20],[30,200],[400,50],[30,20]]: differences -10, -170, 350, 10. Sorted: -170 (30,200), -10 (10,20), 10 (30,20), 350 (400,50). First two to A: 30 + 10, last two to B: 20 + 50. Total 110.
A DP over (people, count in A) also works in O(n²), but the greedy is optimal and simpler.
Optimal Approach
Step 1: Sort costs by a - b ascending.
Step 2: n = len(costs) // 2.
Step 3: Sum costs[i][0] for the first n people and costs[i][1] for the rest.
The exchange argument: swapping any A-person with any B-person in the sorted order can only increase the total.
Time: O(n log n). Space: O(1) beyond sorting.
What Trips People Up in Real Interviews
Assigning each person to their cheaper city. It can put everyone in the same city.
Sorting by costA alone. What matters is the relative saving, costA - costB.
Not justifying the greedy. Give the "start everyone in B, move the best n to A" argument.
Jumping to DP without mentioning the greedy — it works, but the interviewer will ask for the O(n log n) answer.
Solution Code
def twoCitySchedCost(costs):
costs.sort(key=lambda c: c[0] - c[1])
n = len(costs) // 2
return sum(c[0] for c in costs[:n]) + sum(c[1] for c in costs[n:])Frequently Asked Questions
What is the Two City Scheduling problem?
Two City Scheduling gives you `2n` people with the cost of flying each to city A or city B, and asks for the minimum total cost if exactly `n` people go to each city. The greedy insight — sort by how much cheaper A is than B — is the whole problem.
How do you solve Two City Scheduling?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Two City Scheduling?
Two City Scheduling is asked at Bloomberg. It is a medium difficulty problem.
What are common mistakes on Two City Scheduling?
- Assigning each person to their cheaper city. It can put everyone in the same city.
- Sorting by `costA` alone. What matters is the relative saving, `costA - costB`.
- Not justifying the greedy. Give the "start everyone in B, move the best n to A" argument.
- Jumping to DP without mentioning the greedy — it works, but the interviewer will ask for the `O(n log n)` answer.