Send n people to city A and n to city B. Minimize total cost.
Input: costs=[[10,20],[30,200],[400,50],[30,20]] → Output: 110
Input: costs=[[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]] → Output: 1859
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
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)