Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1029.html
1029. Two City Scheduling (Easy)
There are 2N
people a company is planning to interview. The cost of flying the i
-th person to city A
is costs[i][0]
, and the cost of flying the i
-th person to city B
is costs[i][1]
.
Return the minimum cost to fly every person to a city such that exactly N
people arrive in each city.
Example 1:
Input: [[10,20],[30,200],[400,50],[30,20]] Output: 110 Explanation: The first person goes to city A for a cost of 10. The second person goes to city A for a cost of 30. The third person goes to city B for a cost of 50. The fourth person goes to city B for a cost of 20. The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
Note:
1 <= costs.length <= 100
- It is guaranteed that
costs.length
is even. 1 <= costs[i][0], costs[i][1] <= 1000
Related Topics:
Greedy
Solution 1. DP
Let dp[i + 1][j]
be the min cost arranging the first i + 1
people and when j
people go to city A, 0 <= i < N, 0 <= j <= i + 1
.
For dp[i + 1][j]
, we have two options:
- The
i
-th person goes to city A. We getdp[i][j - 1] + A[i][0]
. - The
i
-th person goes to city B. We getdp[i][j] + A[i][1]
. Note thati + 1 > j
because otherwise we don’t have the spot for thei
-th person to go to city B.
dp[i + 1][j] = min(
dp[i][j - 1] + A[i][0], // the i-th person goes to city A
i + 1> j ? dp[i][j] + A[i][1] : INF // the i-th person goes to city B
)
dp[i + 1][0] = sum( A[k][1] | 0 <= k <= i )
// OJ: https://leetcode.com/problems/two-city-scheduling/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& A) {
int N = A.size();
vector<vector<int>> dp(N + 1, vector<int>(N / 2 + 1));
for (int i = 0; i < N; ++i) {
dp[i + 1][0] = dp[i][0] + A[i][1];
for (int j = 1; j <= min(i + 1, N / 2); ++j) {
dp[i + 1][j] = min((i + 1 > j ? dp[i][j] + A[i][1] : INT_MAX), dp[i][j - 1] + A[i][0]);
}
}
return dp[N][N / 2];
}
};
Solution 2. DP with Space Optimization
// OJ: https://leetcode.com/problems/two-city-scheduling/
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& A) {
int N = A.size();
vector<int> dp(N / 2 + 1);
for (int i = 0; i < N; ++i) {
for (int j = min(i + 1, N / 2); j >= 1; --j) {
dp[j] = min((i + 1 > j ? dp[j] + A[i][1] : INT_MAX), dp[j - 1] + A[i][0]);
}
dp[0] += A[i][1];
}
return dp[N / 2];
}
};
Solution 3. Greedy
The smaller cost[i][0] - cost[i][1]
is, the more likely i
-th person should go to city A.
So we can sort the pairs <cost[i][0] - cost[i][1], i>
in ascending order. The first half goes to city A, the second half goes to city B.
// OJ: https://leetcode.com/problems/two-city-scheduling/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& A) {
int N = A.size(), ans = 0;
vector<pair<int, int>> v;
for (int i = 0; i < N; ++i) v.emplace_back(A[i][0] - A[i][1], i);
sort(begin(v), end(v));
for (int i = 0; i < N / 2; ++i) ans += A[v[i].second][0];
for (int i = N / 2; i < N; ++i) ans += A[v[i].second][1];
return ans;
}
};
-
class Solution { public int twoCitySchedCost(int[][] costs) { int length = costs.length; int sum = 0; int[] differences = new int[length]; for (int i = 0; i < length; i++) { sum += costs[i][0]; differences[i] = costs[i][1] - costs[i][0]; } Arrays.sort(differences); int halfLength = length / 2; for (int i = 0; i < halfLength; i++) sum += differences[i]; return sum; } } ############ class Solution { public int twoCitySchedCost(int[][] costs) { Arrays.sort(costs, (a, b) -> { return a[0] - a[1] - (b[0] - b[1]); }); int ans = 0; int n = costs.length >> 1; for (int i = 0; i < n; ++i) { ans += costs[i][0] + costs[i + n][1]; } return ans; } }
-
// OJ: https://leetcode.com/problems/two-city-scheduling/ // Time: O(N^2) // Space: O(N^2) class Solution { public: int twoCitySchedCost(vector<vector<int>>& A) { int N = A.size() / 2; vector<vector<int>> dp(2 * N + 1, vector<int>(N + 1, INT_MAX)); dp[0][0] = 0; for (int i = 0; i < 2 * N; ++i) { for (int j = 0; j <= min(i + 1, N); ++j) { dp[i + 1][j] = min(j - 1 >= 0 ? dp[i][j - 1] + A[i][0] : INT_MAX, j <= i ? dp[i][j] + A[i][1] : INT_MAX); } } return dp[2 * N][N]; } };
-
class Solution: def twoCitySchedCost(self, costs: List[List[int]]) -> int: costs.sort(key=lambda x: x[0] - x[1]) n = len(costs) >> 1 return sum(costs[i][0] + costs[i + n][1] for i in range(n)) ############ # 1029. Two City Scheduling # https://leetcode.com/problems/two-city-scheduling/ class Solution: def twoCitySchedCost(self, costs: List[List[int]]) -> int: n = len(costs) // 2 firstCity = [a for a, b in costs] diff = sorted([b - a for a, b in costs]) return sum(firstCity) + sum(diff[:n])
-
func twoCitySchedCost(costs [][]int) int { sort.Slice(costs, func(i, j int) bool { return costs[i][0]-costs[i][1] < costs[j][0]-costs[j][1] }) ans, n := 0, len(costs)>>1 for i := 0; i < n; i++ { ans += costs[i][0] + costs[i+n][1] } return ans }
-
function twoCitySchedCost(costs: number[][]): number { costs.sort((a, b) => a[0] - a[1] - (b[0] - b[1])); const n = costs.length >> 1; let ans = 0; for (let i = 0; i < n; ++i) { ans += costs[i][0] + costs[i + n][1]; } return ans; }