LeetCode 1029: Two City Scheduling

Problem Restatement

We have 2n people who must each travel to one of two cities: city A or city B.

Exactly n people must go to city A and exactly n must go to city B.

The cost to send person i to city A is costs[i][0] and to city B is costs[i][1].

We need to return the minimum total cost.

The official constraints state that 2 <= costs.length <= 200, costs.length is even, and 1 <= costs[i][0], costs[i][1] <= 10^4.

Input and Output

Function shape:

def twoCitySchedCost(costs: list[list[int]]) -> int:
    ...

Examples

Example 1:

costs = [[10,20],[30,200],[400,50],[30,20]]

Send persons 0, 1 to A: 10 + 30 = 40. Send persons 2, 3 to B: 50 + 20 = 70. Total: 110.

Answer:

110

Key Insight

Start by sending everyone to city A. Cost = sum(costs[i][0]).

Now we need to switch n people to city B. Switching person i from A to B costs an extra:

costs[i][1] - costs[i][0]

This is the “refund” (can be negative, meaning cheaper).

To minimize total cost, sort by this difference and switch the n people with the smallest differences.

Algorithm

1. Compute base cost: send everyone to A.
2. Compute diff[i] = costs[i][1] - costs[i][0] for each person.
3. Sort diff.
4. Add the n smallest differences to the base cost.
5. Return total.

Correctness

Sending everyone to A gives the base cost. Switching person i to B changes the cost by costs[i][1] - costs[i][0].

We must switch exactly n people. To minimize the total change, pick the n people with the smallest switching cost (most negative differences benefit us most).

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

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

Code Explanation

Sort by the cost difference (benefit of going to B vs A):

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

Those with the smallest (most negative) difference benefit most from going to B.

Send the first n (cheapest to redirect to B) to B, and the last n to A:

sum(costs[i][0] for i in range(n)) + sum(costs[i][1] for i in range(n, 2 * n))

Wait — those sorted first (smallest b - a) are cheapest to send to B. So send them to B and the rest to A.

After sorting by costB - costA, the first n people are cheapest to send to city B relative to city A, and the remaining n people go to city A. Therefore:

• First n: send to B → costs[i][1]
• Last n: send to A → costs[i][0]

Testing

def run_tests():
    s = Solution()

    assert s.twoCitySchedCost([[10,20],[30,200],[400,50],[30,20]]) == 110
    assert s.twoCitySchedCost([[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]) == 1859

    print("all tests passed")

run_tests()