Two City Scheduling

How it works

We can simplify the greedy approach by sorting the original array directly by cost[B] - cost[A] without creating extra tuples. After sorting, the first n entries favor city B, and the last n favor city A.

Steps

1. Sort the costs array by cost[1] - cost[0] (ascending).
2. For the first n people, add their city B cost.
3. For the last n people, add their city A cost.
4. Return the total.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(1) or O(n) depending on the sorting algorithm.

Things to watch for

Sorting by the Wrong Cost Difference

The greedy approach requires sorting by cost[B] - cost[A] to determine which people benefit most from going to city B. A common mistake is sorting by cost[A] - cost[B] or by individual costs rather than the difference. This leads to suboptimal assignments because you are not correctly identifying the relative advantage of each city for each person.

Not Enforcing Equal Distribution to Both Cities

The problem requires exactly n people to go to city A and n people to go to city B. A greedy approach that simply sends each person to their cheaper city without tracking counts will likely result in an unbalanced distribution. Always ensure your solution enforces the constraint that exactly half go to each city.

Off-by-One Errors in Index Calculation for DP

In the bottom-up DP approach, the person index i is derived from aCount + bCount. A common error is using i instead of i - 1 when accessing the costs array, or incorrectly computing which person corresponds to a given state. This leads to accessing wrong cost values or array index out of bounds errors.

from typing import List

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key=lambda x: x[1] - x[0])
        n, res = len(costs) // 2, 0

        for i in range(n):
            res += costs[i][1] + costs[i + n][0]
        return res

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(), costs.end(), [](const auto& a, const auto& b) {
            return (a[1] - a[0]) < (b[1] - b[0]);
        });

        int n = costs.size() / 2, res = 0;
        for (int i = 0; i < n; i++) {
            res += costs[i][1] + costs[i + n][0];
        }
        return res;
    }
};