[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