05 August 2008
公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为 costs[i][1]。返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达
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;
}
}