描述
今天有N个面试者需要面试，公司安排了两个面试的城市A和B，每一个面试者都有到A城市的开销costA和到B城市的开销costB。公司需要将面试者均分成两拨，使得total cost最小。
- N是偶数
- 2≤N≤105
- 答案确保在int范围内
- 1≤costA,costB≤106
题目要求去A的人数和去B的人数相等。
在线评测地址：领扣题库官网
样例1
输入:
cost = [[5,4],[3,6],[1,8],[3,9]]
输出:
14
说明:
第一个和第二个人去B城市，剩下的去A城市解题思路
对于每一个人去A城市的距离减去B城市的距离，从小到大进行排序，前一半的人去A城市，后一半的人去B城市。
复杂度分析
时间复杂度：O(nlogn)
需要进行排序，排序算法时间为nlogn。
空间复杂度：O(1)
不需要开辟新的空间。
源代码
public class Solution {
public int TotalCost(List<List<Integer>> cost) {
Comparator<List<Integer>> cmp = new Comparator<List<Integer>>() {
public int compare(List<Integer> first,List<Integer> second) {
if (first.get(1) - first.get(0) == second.get(1) - second.get(0)) {
return 0;
}
else if (first.get(1) - first.get(0) < second.get(1) - second.get(0)) {
return -1;
}
else {
return 1;
}
}
};
Collections.sort(cost, cmp);
int answer = 0;
int length = cost.size();
int j = 0;
for (int i = 0; i < length; i++) {
if (2 * j < length) {
answer += cost.get(i).get(1);
}
else {
answer += cost.get(i).get(0);
}
j++;
}
return answer;
}
}更多题解参考：九章官网solution
