Two City Scheduling: Greedy Cost Optimization

You are given 2n people. Each person i has two costs: costs[i] = [aCosti, bCosti], where aCosti is the cost of flying them to city A and bCosti is the cost of flying them to city B. Return the minimum total cost to fly exactly n people to each city.

This is LeetCode 1029: Two City Scheduling, and it is one of the cleanest examples of the greedy sorting pattern. The trick is not to think about which city is cheapest for each person in isolation. Instead, you compare how much you save by picking one city over the other, then sort on that difference.

Why this problem matters

Greedy problems often hide behind the illusion of needing brute force. With 2n people and two choices per person, there are C(2n, n) ways to split them. That grows fast. But the constraint that exactly n must go to each city gives you just enough structure to apply a greedy argument.

The key idea, sorting by the relative cost difference, shows up in many optimization problems: task scheduling, resource allocation, and load balancing. If you can prove that a local decision (sort by savings, then assign greedily) leads to a global optimum, you avoid searching the entire solution space.

The key insight

For each person, compute the "savings" of sending them to city A instead of city B: savings = costA - costB. A negative savings means city A is the better deal. A positive savings means city B is cheaper.

Now sort all people by this savings value in ascending order. The people at the front of the sorted list benefit the most from going to city A (they have the most negative savings). The people at the end benefit the most from going to city B (they have the most positive savings).

Since you need exactly n people in each city, assign the first n to city A and the last n to city B. This greedy assignment minimizes total cost because every swap between the two halves would increase the total: you would be moving someone from their cheaper city to their more expensive one.

The solution

def two_city_sched_cost(costs: list[list[int]]) -> int:
    costs.sort(key=lambda c: c[0] - c[1])
    n = len(costs) // 2
    total = 0
    for i in range(n):
        total += costs[i][0]
    for i in range(n, 2 * n):
        total += costs[i][1]
    return total

The sort arranges people by how much cheaper city A is relative to city B. After sorting, the first n entries are the people who save the most by going to city A, so you add their costA. The remaining n entries are better off in city B, so you add their costB. The result is the minimum possible total cost.

Visual walkthrough

Let's trace through costs = [[10,20],[30,200],[400,50],[30,20]]. There are 4 people, so n = 2. We need 2 in city A and 2 in city B.

The sorted order puts the people with the most negative savings first. Person 1 saves 170 by going to city A instead of B. Person 2 saves 350 by going to city B instead of A. The greedy assignment respects these preferences and produces the minimum total cost of 110.

Complexity analysis

Time is O(n log n) where n is the number of people (2n in the problem statement, but sorting 2n elements is still O(n log n)). The sort dominates. The final summation loop is O(n).

Space is O(1) extra if you sort in place. Python's list.sort() uses Timsort which requires O(n) auxiliary space in the worst case, but conceptually the algorithm needs no additional data structures beyond the input.

The building blocks

1. Sorting by a derived key

The core technique is computing a value that does not exist in the input (the savings costA - costB) and sorting by it:

costs.sort(key=lambda c: c[0] - c[1])

This pattern appears whenever the natural ordering of the data is not what you need. Instead of sorting by costA or costB alone, you sort by the relationship between them. You will see the same idea in problems like Advantage Shuffle (sort by relative strength) and Boats to Save People (sort by weight to pair efficiently).

2. Greedy split after sorting

Once the array is sorted, the assignment is mechanical: first half to one group, second half to the other:

n = len(costs) // 2
for i in range(n):
    total += costs[i][0]
for i in range(n, 2 * n):
    total += costs[i][1]

This "sort then split" strategy works because the sort guarantees that any swap between the two halves would make the total worse. The proof is an exchange argument: if person i (in the city A half) and person j (in the city B half) were swapped, the change in cost would be (costs[i][1] - costs[i][0]) + (costs[j][0] - costs[j][1]). Because i has a smaller savings value than j, this sum is always non-negative, meaning the swap never helps.

Edge cases

• All costs identical: every person has the same [a, b]. Sorting changes nothing, and any split gives the same total. The algorithm handles this correctly.
• One city is always cheaper: if costA is less than costB for every person, you would want everyone in city A, but you are forced to send half to city B. The sort ensures the people who suffer the least from going to B are the ones assigned there.
• n = 1: only two people. Sort them, send the first to A and the second to B. Trivial case but worth verifying.
• Very large cost differences: no overflow issues in Python, but in languages with fixed-width integers, costA - costB could overflow if costs are near the integer limits.
• Already sorted input: the algorithm still works. Sorting a sorted array is O(n) with Timsort.

From understanding to recall

The greedy logic here is clean: sort by costA - costB, assign the first half to A, the second half to B. But in an interview, the hard part is remembering why this works and being able to articulate the exchange argument that proves optimality.

The details that trip people up are subtle. Do you sort ascending or descending? Do you use costA - costB or costB - costA? Which half goes to which city? These are recall problems, not understanding problems, and they are exactly what spaced repetition is designed to solve.

After a few rounds of writing the sort key and the split logic from memory, you stop second-guessing the direction. You see "minimize cost with a balanced split" in a problem, and the template comes out automatically.

Related posts

• Assign Cookies - Another greedy problem where sorting by a derived property lets you make optimal local decisions
• Boats to Save People - Sort then use two pointers to pair elements greedily, a close cousin of the "sort then split" pattern
• Advantage Shuffle - Greedy matching after sorting, where relative comparison between two arrays drives the strategy

CodeBricks breaks Two City Scheduling into its sort-by-savings and greedy-split building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy optimization problem shows up in your interview, you do not fumble the sort direction. You just write it.