The Two City Scheduling problem asks you to help an organization minimize travel costs for sending people to two cities for a conference. You are given an array costs where costs[i] = [aCost, bCost] represents the cost of flying the ith person to city A and city B, respectively.
Key constraints: Each person is assigned to exactly one city, and you must split the group evenly between the two cities. There is always at least one valid solution, and you cannot reuse people or assign someone to both cities.
At first glance, it might seem like we need to try all possible ways of dividing the people into two groups of N, which would be a brute-force approach. But that's computationally expensive, especially as the group grows larger.
Instead, we notice that for each person, sending them to city A or city B has a certain cost difference. If we always sent everyone to the cheaper city for them, we might end up with an unbalanced assignment (more than N people in one city).
The key insight is to consider the relative savings for each person between the two cities, and to prioritize sending people to the city where their cost advantage is greatest, while still ensuring an even split.
We want to minimize the total cost while sending exactly N people to each city. Here is a step-by-step approach:
costA - costB).
This approach works because sorting by the cost difference ensures that we assign people to the city where they offer the greatest savings, while still keeping the split even.
Let's say costs = [[10, 20], [30, 200], [400, 50], [30, 20]]. There are 4 people (2N = 4, so N = 2).
Total = 30 + 10 + 20 + 50 = 110
This is the minimum possible cost for assigning 2 people to each city.
class Solution:
def twoCitySchedCost(self, costs):
# Sort by cost difference
costs.sort(key=lambda x: x[0] - x[1])
n = len(costs) // 2
total = 0
# First N to city A, rest to city B
for i in range(n):
total += costs[i][0]
for i in range(n, 2*n):
total += costs[i][1]
return total
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b) {
return (a[0] - a[1]) < (b[0] - b[1]);
});
int n = costs.size() / 2;
int total = 0;
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;
}
};
class Solution {
public int twoCitySchedCost(int[][] costs) {
Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
int n = costs.length / 2;
int total = 0;
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;
}
}
var twoCitySchedCost = function(costs) {
costs.sort((a, b) => (a[0] - a[1]) - (b[0] - b[1]));
let n = costs.length / 2;
let total = 0;
for (let i = 0; i < n; i++) {
total += costs[i][0];
}
for (let i = n; i < 2 * n; i++) {
total += costs[i][1];
}
return total;
};
O(C(2N, N)) (combinatorial explosion). This is not practical for large inputs.
O(N \log N) time, where N is the number of people. Assigning costs is O(N).
O(1) extra space (if sorting is in-place) or O(N) if a new array is created.
The sorting-based solution is efficient and scalable.
The Two City Scheduling problem is a classic example of using sorting to optimize selection under constraints. By focusing on the cost differences and sorting accordingly, we can efficiently assign people to cities to minimize total cost, while maintaining the required balance. This approach leverages a greedy strategy that is both simple and powerful.