"Two City Scheduling" is a logistical optimization problem. A company is flying 2n people to two different cities (City A and City B). Each person has a different cost for flying to City A versus City B. The constraint is that exactly n people must go to City A and exactly n people must go to City B. You need to calculate the minimum total cost to fly all 2n people to their assigned cities.
This "Two City Scheduling interview question" is a favorite at companies like Bloomberg and Meta because it's a perfect test of "Greedy" thinking. While it can be solved with dynamic programming, the greedy approach is much more efficient and elegant. Interviewers look for the insight that the problem isn't about the absolute costs, but rather the opportunity cost (the difference in cost) of sending a person to one city over the other.
The "Array, Sorting, Greedy interview pattern" is the most effective way to solve this. The core strategy is to calculate the difference costA - costB for each person. This difference represents how much extra it costs to send someone to City A instead of City B. You then sort all people by this difference in ascending order. The first n people in the sorted list are the ones for whom going to City A is the most "profitable" (or least expensive) compared to City B, so they are sent to City A. The remaining n go to City B.
Suppose you have 4 people with costs [A, B]:
The most common mistake is trying to use a complex DP approach when the greedy one is sufficient. Another error is sorting by the absolute cost of City A or City B, which doesn't lead to the global minimum because it ignores the cost of the other city. Some candidates also forget to divide the population exactly in half, leading to an invalid distribution.
To excel in the "Two City Scheduling coding problem," practice "Sorting by Relative Gain." Whenever a problem asks you to distribute items into two equal groups to minimize/maximize a total, look for a way to sort them by the "benefit" of choosing one group over the other.
