[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]]
输出: 
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