Two City Scheduling

Share

Send n people to city A and n to city B. Minimize total cost.

Example 1
Input: costs=[[10,20],[30,200],[400,50],[30,20]] → Output: 110
Example 2
Input: costs=[[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]] → Output: 1859

Solution Approach

Sort by the difference (costA - costB). Send first n to A, rest to B.

  • Sort by costA - costB
  • First n people go to A (cheaper relative to B)
  • Last n people go to B
  • Sum all selected costs
Java
public int twoCitySchedCost(int[][] costs) {
    Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
    int total = 0, n = costs.length / 2;
    for (int i = 0; i < n; i++) total += costs[i][0];
    for (int i = n; i < 2 * n; i++) total += costs[i][1];
    return total;
}
  • Time Complexity: O(n log n)
  • Space Complexity: O(1)