[leetcode/lintcode 题解] 算法面试真题详解：安排面试城市

描述
今天有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]]
第一个和第二个人去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

本文转自网络，原文链接：https://developer.aliyun.com/article/784285
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！