LeetCode - Two City Scheduling
Problem description
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:
1
2
3
4
5
6
7
8
9
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
Analysis
Basically, we can use A-B to sort the array and we can get result. The thought is that if we have two bucket to store the same size of item, and its cost is differ. Then we can use A-B to get the result. if A1-B1 < A2-B2, then we can have A1+B2 < A2+B1, so if we want to get the min cost, then we should choose the A1 B2 group, which is the smaller one of A-B to go to the A bucket.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int twoCitySchedCost(int[][] costs) {
// Sort by a gain which company has
// by sending a person to city A and not to city B
Arrays.sort(costs, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o1[1] - (o2[0] - o2[1]);
}
});
int total = 0;
int n = costs.length / 2;
// To optimize the company expenses,
// send the first n persons to the city A
// and the others to the city B
for (int i = 0; i < n; ++i) total += costs[i][0] + costs[i + n][1];
return total;
}
}
What to improve
- Greedy needs to practice more.