Medium

题目描述

一家公司计划面试 2n 个人。给你一个数组 costs ，其中 costs[i] = [aCosti, bCosti] ，第 i 个人飞往 a 市的费用为 aCosti ，飞往 b 市的费用为 bCosti 。

返回将每个人都飞到 a、b 中某座城市的最低费用，要求每个城市都有 n 个人抵达。

示例 1：

输入：costs = [[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去往城市 A，费用为 10。
第二个人去往城市 A，费用为 30。
第三个人去往城市 B，费用为 50。
第四个人去往城市 B，费用为 20。
最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。

示例 2：

输入：costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
输出：1859

示例 3：

输入：costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
输出：3086

提示：

  • 2 * n == costs.length
  • 2 <= costs.length <= 100
  • costs.length 是偶数
  • 1 <= aCosti, bCosti <= 1000

解题思路

这是一道经典的贪心算法题。关键思路是如何决定哪些人去城市A，哪些人去城市B。

核心思想： 我们不能简单地选择每个人的最小费用，因为必须保证两个城市各有n个人。正确的思路是考虑机会成本。

对于第i个人：

  • 去城市A的机会成本 = costs[i][0] - costs[i][1]（选择A而放弃B的额外代价）
  • 去城市B的机会成本 = costs[i][1] - costs[i][0]（选择B而放弃A的额外代价）

算法步骤：

  1. 计算每个人去城市A相对于去城市B的差值：costs[i][0] - costs[i][1]
  2. 按照这个差值升序排序
  3. 差值最小的前n个人去城市A，剩下n个人去城市B

这样保证了总费用最小，因为我们优先让那些"去A比去B更划算"的人去A城市。

时间复杂度分析： 主要是排序的O(n log n) 空间复杂度分析： 排序需要O(n)额外空间

代码实现

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b) {
            return (a[0] - a[1]) < (b[0] - b[1]);
        });
        
        int totalCost = 0;
        int n = costs.size() / 2;
        
        for (int i = 0; i < n; i++) {
            totalCost += costs[i][0];  // 前n个人去城市A
        }
        
        for (int i = n; i < 2 * n; i++) {
            totalCost += costs[i][1];  // 后n个人去城市B
        }
        
        return totalCost;
    }
};

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        # 按照去城市A相对于城市B的差值排序
        costs.sort(key=lambda x: x[0] - x[1])
        
        total_cost = 0
        n = len(costs) // 2
        
        # 前n个人去城市A
        for i in range(n):
            total_cost += costs[i][0]
        
        # 后n个人去城市B
        for i in range(n, 2 * n):
            total_cost += costs[i][1]
        
        return total_cost

public class Solution {
    public int TwoCitySchedCost(int[][] costs) {
        Array.Sort(costs, (a, b) => (a[0] - a[1]).CompareTo(b[0] - b[1]));
        
        int totalCost = 0;
        int n = costs.Length / 2;
        
        for (int i = 0; i < n; i++) {
            totalCost += costs[i][0];  // 前n个人去城市A
        }
        
        for (int i = n; i < 2 * n; i++) {
            totalCost += costs[i][1];  // 后n个人去城市B
        }
        
        return totalCost;
    }
}

var twoCitySchedCost = function(costs) {
    costs.sort((a, b) => (a[0] - a[1]) - (b[0] - b[1]));
    
    let totalCost = 0;
    const n = costs.length / 2;
    
    for (let i = 0; i < n; i++) {
        totalCost += costs[i][0];  // 前n个人去城市A
    }
    
    for (let i = n; i < 2 * n; i++) {
        totalCost += costs[i][1];  // 后n个人去城市B
    }
    
    return totalCost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n log n)主要消耗在排序操作上
空间复杂度O(1)只使用常数级额外空间（不考虑排序的栈空间）

相关题目