A company is planning to interview 2n
people. Given the array costs
where costs[i] = [aCosti, bCosti]
, the cost of flying the ith
person to city a
is aCosti
, and the cost of flying the ith
person to city b
is bCosti
.
Return the minimum cost to fly every person to a city such that exactly n
people arrive in each city.
Example 1:
Input: costs = [[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.
Example 2:
Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]] Output: 1859
Example 3:
Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]] Output: 3086
Constraints:
2 * n == costs.length
2 <= costs.length <= 100
costs.length
is even.1 <= aCosti, bCosti <= 1000
Companies:
Bloomberg
Related Topics:
Array, Greedy, Sorting
Let dp[i + 1][j]
be the min cost arranging the first i + 1
people and when j
of them 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]
(j - 1 >= 0
). - The
i
-th person goes to city B. We getdp[i][j] + A[i][1]
(j <= i
).
dp[i + 1][j] = min(
j - 1 >= 0 ? dp[i][j - 1] + A[i][0] : INF, // the i-th person goes to city A
j <= i ? dp[i][j] + A[i][1] : INF // the i-th person goes to city B
)
dp[0][0] = 0
The answer is dp[2N][N]
.
// OJ: https://leetcode.com/problems/two-city-scheduling/
// Author: github.com/lzl124631x
// 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];
}
};
// OJ: https://leetcode.com/problems/two-city-scheduling/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& A) {
int N = A.size() / 2;
vector<int> dp(N + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i < 2 * N; ++i) {
for (int j = min(i + 1, N); j >= 0; --j) {
dp[j] = min(j - 1 >= 0 ? dp[j - 1] + A[i][0] : INT_MAX, j <= i ? dp[j] + A[i][1] : INT_MAX);
}
}
return dp[N];
}
};
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 array in ascending order of cost[i][0] - cost[i][1]
. The first half goes to city A, the second half goes to city B.
// OJ: https://leetcode.com/problems/two-city-scheduling/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& A) {
int N = A.size() / 2, ans = 0;
sort(begin(A), end(A), [](auto &a, auto &b) { return (a[0] - a[1]) < (b[0] - b[1]); });
for (int i = 0; i < 2 * N; ++i) ans += A[i][i >= N];
return ans;
}
};