算法

(贪心) $O(nlogn)$

题意是有$2n$个人，然后要往$A$和$B$分别塞$n$个人，要求$cost$最小。对于每两个人，我们可以假设他们去$A$或$B$，然后就有两种情况：

• $i$去$A$，$i+1$去$B$：$costs[i][0] + costs[i+1][1]$
• $i$去$B$，$i+1$去$A$：$costs[i][1] + costs[i+1][0]$

然后我们选择两种情况中和更小的那一个，这样才能使得总的$cost$最小。作一下变形就是$costs[i][0]-costs[i][1]$，对于差值比较小的那一个让他去$A$，而对于差值比较大的那一个就让他去$B$。然后对数组排个序，排序规则是上面的式子，对于前$n$个人去$A$，后$n$个人去$B$。

Java 代码

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        // i  i+1
        // costs[i][0] + csots[i + 1][1]
        // costs[i][1] + costs[i + 1][0]
        // costs[i][0] - costs[i][1]
        Arrays.sort(costs, (o1, o2) -> Integer.compare(o1[0] - o1[1], o2[0] - o2[1]));
        int total = 0;
        int n = costs.length;
        for (int i = 0; i < n; ++i) {
            if (i < n / 2) total += costs[i][0];
            else total += costs[i][1];
        }
        return total;
    }
}