https://leetcode.com/problems/two-city-scheduling/
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.lengthis even. 1 <= costs[i][0], costs[i][1] <= 1000
Greedy
Sort by cost_a – cost_b, Choose the first n/2 people for A, rest for B
https://leetcode.com/problems/two-city-scheduling/discuss/278716/C%2B%2B-O(n-log-n)-sort-by-savings
How much money can we save if we fly a person to A vs. B? To minimize the total cost, we should fly the person with the maximum saving to A, and with the minimum - to B.
Example: [30, 100], [40, 90], [50, 50], [70, 50].
Savings: 70, 50, 0, -20.
Savings: 70, 50, 0, -20.
Obviously, first person should fly to A, and the last - to B.
Solution
We sort the array by the difference between costs for A and B. Then, we fly first
N people to A, and the rest - to B.int twoCitySchedCost(vector<vector<int>>& cs, int res = 0) {
sort(begin(cs), end(cs), [](vector<int> &v1, vector<int> &v2) {
return (v1[0] - v1[1] < v2[0] - v2[1]);
});
for (auto i = 0; i < cs.size() / 2; ++i) {
res += cs[i][0] + cs[i + cs.size() / 2][1];
}
return res;
}
Optimized Solution
Actually, we do not need to perfectly sort all cost differences, we just need the biggest savings (to fly to A) to be in the first half of the array. So, we can use the quick select algorithm (
nth_element in C++) and use the middle of the array as a pivot.
This brings the runtime down from 8 ms to 4 ms (thanks @popeye1 for the tip!)
int twoCitySchedCost(vector<vector<int>>& cs, int res = 0) {
nth_element(begin(cs), begin(cs) + cs.size() / 2, end(cs), [](vector<int> &a, vector<int> &b) {
return (a[0] - a[1] < b[0] - b[1]);
});
for (auto i = 0; i < cs.size() / 2; ++i) {
res += cs[i][0] + cs[i + cs.size() / 2][1];
}
return res;
}
Complexity Analysis
Runtime: O(n log n). We sort the array then go through it once. The second solution has a better average case runtime.
Memory: O(1). We sort the array in-place
Memory: O(1). We sort the array in-place
https://leetcode.com/problems/two-city-scheduling/discuss/278898/Java-2ms-sorting-solution-with-explanation
The cost of sending a flyer to city B is relative to the cost of sending them to city A. If we send them to city B, then we have to send some other flyer to city A because we need N people in both cities. We could generally find the highest costs to B and send those people to A, but if they also have a high cost to A, then we didn't save much. Similarly, if we find the lowest costs to B and send those people to B, then we might not have saved much money over sending them to A - and meanwhile if that action caused us to send someone to A who cost us a lot more, we've lost money overall.
Another way to look at it is that each person costs a certain amount to fly regardless of the city they go to, then they cost an additional premium to fly to one of the cities over the other. If their cost pair is
[1000,1001] basically that person costs 1000 no matter what and we are only looking at saving or spending that extra dollar. We could reduce the solution by subtracting the minimum cost from both sides of each pair and then looking at optimizing the differential costs. That person's costs would then be fixed=1000, relative=[0,1]. It produces the same answer, but it seems simpler because now everyone has a 0 (relative) cost for one city and a non-zero cost to the other. The solution at this point would be fairly simple - send the people with the largest differential costs to the city of their 0 relative cost, and then when you get the people with large differences assigned you end up with a lot of people with small differences, you keep doing this, saving less and less each time until you might end up with a bunch of people who all cost extra money to send to one city, but you've already assigned everyone you need to the other city. For example, the cost pairs [10,5], [10,7], [10,8], [5,10] could be made differential and you would get the costs fixed = [5,7,8,5], differentials=[[5,0],[3,0],[2,0],[0,5]] You know it will cost you at least 5+7+8+5 == 25 to send everyone, but how can you save the remaining costs? You obviously send the first person to city B and the last to city A and now you have one more for each city and the remainig differential costs are [3,0],[2,0]. You can't send them both to city B since that would leave the cities improperly staffed, so you have to pick one to send to A and the other to B. Clearly you send the one that costs the least extra to send to A which is the latter of the two.
Subtracting out the fixed costs really makes it rather obvious who to send where, you just sort them in the order from most costly to send to A, to most costly to send to B and then send the first half to city B and the second half to city A. It seems odd to have a dual-sort where one value is decreasing while the other is increasing, but since all cost pairs have one zero and one non-zero it is pretty obvious that the sorted order starts with the pairs that have a zero differential cost for B and they are in order of decreasing relative cost to send to A, then that is followed by all of the people who have a zero differential cost to go to A in the order of increasing cost to send them to B. It would look something like this:
[10,0],[5,0],[3,0],...[0,2],[0,5],[0,100] It's pretty clear that the first person goes to B and the last one goes to A and choosing the first half of the list to go to B would minimize the relative costs for city B and the latter half would minimize the relative costs to go to A.
But, you don't need to actually extract the fixed costs, you can do this with the original amounts just by looking at the difference between the numbers. Creating a bunch of relative costs just gives you a bunch of pairs of numbers were one of them is 0. If you subtract the A cost from the B cost, you get a single number that sorts the people by the relative cost to send them to B. You then send the ones with the highest relative B cost to A and vice versa.
Thus the technique here, sort the list first by the B-A cost, then the beginning of the list (smallest values of "relative cost to send to B") are the ones you would rather send to B and the ones at the end you'd rather send to A.
public int twoCitySchedCost(int[][] costs) {
Arrays.sort(costs, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return (a[1] - a[0]) - (b[1] - b[0]);
}
});
int cost = 0;
for (int i = 0; i < costs.length / 2; i++) {
cost += costs[i][1] + costs[costs.length-i-1][0];
}
return cost;
}public int twoCitySchedCost(int[][] costs) {
Arrays.sort(costs, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return a[0] - a[1] - (b[0] - b[1]);
}
});
int res = 0;
for (int i = 0; i < costs.length / 2; i++) {
res += costs[i][0];
}
for (int i = costs.length / 2; i < costs.length;i++) {
res += costs[i][1];
}
return res;
}X. DP
https://zxi.mytechroad.com/blog/tag/contest/
dp[i][j] := min cost to put j people into city A for the first i people
dp[0][0] = 0
dp[i][0] = dp[i -1][0] + cost_b
dp[i][j] = min(dp[i – 1][j] + cost_b, dp[i – 1][j – 1] + cost_a)
ans := dp[n][n/2]
Time complexity: O(n^2)
Space complexity: O(n^2)
https://leetcode.com/problems/two-city-scheduling/discuss/278731/Java-DP-Easy-to-Understand
dp[i][j] represents the cost when considering first (i + j) people in which i people assigned to city A and j people assigned to city B.
my explanation here, just in case other people need this:
public int twoCitySchedCost(int[][] costs) {
int N = costs.length / 2;
int[][] dp = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
dp[i][0] = dp[i - 1][0] + costs[i - 1][0];
}
for (int j = 1; j <= N; j++) {
dp[0][j] = dp[0][j - 1] + costs[j - 1][1];
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
dp[i][j] = Math.min(dp[i - 1][j] + costs[i + j - 1][0], dp[i][j - 1] + costs[i + j - 1][1]);
}
}
return dp[N][N];
}https://leetcode.com/problems/two-city-scheduling/discuss/278799/Java-Easy-to-understand-DFS-with-cache-solution
public int twoCitySchedCost(int[][] costs) {
int len = costs.length / 2;
int[][] memo = new int[len + 1][len + 1];
dfs(memo, costs, len, len, 0);
return memo[len][len];
}
private int dfs(int[][] memo, int[][] costs, int A, int B, int index) {
if (index == costs.length) {
return 0;
}
if (memo[A][B] != 0) {
return memo[A][B];
}
int costA = costs[index][0];
int costB = costs[index][1];
if (A == 0 && B > 0) {
memo[A][B] = costB + dfs(memo, costs, A, B - 1, index + 1);
} else if (B == 0 && A > 0) {
memo[A][B] = costA + dfs(memo, costs, A - 1, B, index + 1);
} else {
int sumA = costA + dfs(memo, costs, A - 1, B, index + 1);
int sumB = costB + dfs(memo, costs, A, B - 1, index + 1);
memo[A][B] = Math.min(sumA, sumB);
}
return memo[A][B];
}
公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为 costs[i][1]。
返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达。
样例
示例：
输入：[[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 A 市，费用为 10。
第二个人去 A 市，费用为 30。
第三个人去 B 市，费用为 50。
第四个人去 B 市，费用为 20。
最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。
提示：
1 <= costs.length <= 100
costs.length 为偶数
1 <= costs[i][0], costs[i][1] <= 1000(排序)
这道题先假设所有的人都去A市，然后我们只需要选取去B市的费用与去A市的费用的差最小的N个人改去B市即可。
时间复杂度分析：排序时间复杂度
- 输入一个长度是2*N的二维数组， a[i][0]表示第i个人分配到A城市的价格， a[i][1]表示第i个人分配到B城市的价格
- 把这2*N个数组分成长度相等的两份， 其中一半选择A， 另外一半选择B， 问总共最小的总共价格是多少？
- 这个题目暴力肯定不行， 直接简单的贪心选择最小的也不对， 卡壳了好一会儿。
还好后来终于想出来了，感觉这样的题目能不能分析出来很没有把握。
- 假设所有的人都选择城市A， 这时候sum=sum{a[i][0]},
然后要选择一半的人改成B， 这个时候, 选择某一个人对sum的影响是d=a[i][1]-a[i][0],
那么， 我们要让结果最小， 就需要让这个d最小， 那按照这个d对数组排序，然后选择最小的一半就好
public int twoCitySchedCost(int[][] costs) {
Arrays.sort(costs, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
int v1 = a[1] - a[0];
int v2 = b[1] - b[0];
return v1-v2;
}
});
int sum = 0;
for(int[] cost: costs) {
sum += cost[0];
}
for(int i = 0; i < costs.length/2; ++i) {
sum += costs[i][1] - costs[i][0];
}
return sum;
}
X. Video
花花酱 LeetCode Weekly Contest 133 (1029,1030,1031,1032)
花花酱 LeetCode Weekly Contest 133 (1029,1030,1031,1032)
Leetcode 1029 - Two City Scheduling | Greedy Algo | Company Interview Tags: Bloomberg
