1029. 两地调度

解题思路：贪心 + 排序

怎么贪：

培养一个思维：我们不是单独拿一个城市，而是假设所有面试者都去B，那么挑出来去A的应该是代价最小的即按照 cost[i][0] - cost[i][1] 排升序

也就是 cost[a][0] - cost[a][1] - (cost[b][0] - cost[b][1]) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o1[1] - (o2[0] - o2[1]);
            }
        });
        int n = costs.length;
        int splitN = n / 2;
        int i = 0;
        int aSum = 0, bSum = 0;
        for (; i < splitN; i++) {
            aSum += costs[i][0];
        }
        for (; i < n; i++) {
            bSum += costs[i][1];
        }
        return aSum + bSum;
    }
}