1029. Two City Scheduling
Asked at Bloomberg
Difficulty
Medium
Time
O(n log n)
Space
O(1)
Pattern
Array
Companies
1
Problem
A company is interviewing 2n people. For each person i, you are given costs[i] = [aCost, bCost]: the price of flying that person to city A, and the price of flying them to city B.
You must send every person to exactly one city, and you must end up with exactly n people in city A and exactly n people in city B. Return the minimum total cost of such a plan.
The hard part is the balance rule. If you just send each person to their cheaper city, you may end up with the wrong number of people in each city. So you have to trade off: some people must fly to their more expensive city to keep the counts equal.
Pick n people for each city
Constraints
- ●
2 * n == costs.length - ●
2 <= costs.length <= 100 - ●
costs.length is even - ●
1 <= aCosti, bCosti <= 1000
Examples
costs = [[10,20],[30,200],[400,50],[30,20]]110costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]1859costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]3086Asked At
1 companies| 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.
Sort by how much A saves over B
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
O(n log n) timedef 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 runs in O(n log n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.