1029. 两地调度

来源第 133 场周赛 Q1难度中等分数1348

题目描述

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

返回将每个人都飞到 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 <= aCost_i, bCost_i <= 1000

解法

方法一：排序 + 贪心

思考

从 \(2n\) 人中选 \(n\) 个去 \(A\)、其余去 \(B\)，子集枚举不可行。先让所有人去 \(B\)，再改派 \(n\) 人去 \(A\)，总费用的变化是 \(aCost-bCost\)。

减少量越大（差值越小）的人越应该改去 \(A\)。按 \(aCost-bCost\) 升序排序后，前 \(n\) 人去 \(A\)、后 \(n\) 人去 \(B\)，即为最优分配。

排序后对半求和即可。

我们不妨先假设所有人都去 \(b\) 市，然后我们要从中选出 \(n\) 个人去 \(a\) 市，使得总费用最小。如果一个人去 \(a\) 市的费用比去 \(b\) 市的费用小，我们把这个人从 \(b\) 市调到 \(a\) 市，这样总费用就会减少。因此，我们可以将所有人按照去 \(a\) 市的费用与去 \(b\) 市的费用的差值从小到大排序，然后选出前 \(n\) 个人去 \(a\) 市，剩下的人去 \(b\) 市，这样总费用就是最小的。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 为数组 costs 的长度。

相似题目：

2611. 老鼠和奶酪

Python3JavaC++GoTypeScript

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key=lambda x: x[0] - x[1])
        n = len(costs) >> 1
        return sum(costs[i][0] + costs[i + n][1] for i in range(n))

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, (a, b) -> { return a[0] - a[1] - (b[0] - b[1]); });
        int ans = 0;
        int n = costs.length >> 1;
        for (int i = 0; i < n; ++i) {
            ans += costs[i][0] + costs[i + n][1];
        }
        return ans;
    }
}

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 n = costs.size() / 2;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += costs[i][0] + costs[i + n][1];
        }
        return ans;
    }
};

func twoCitySchedCost(costs [][]int) (ans int) {
    sort.Slice(costs, func(i, j int) bool {
        return costs[i][0]-costs[i][1] < costs[j][0]-costs[j][1]
    })
    n := len(costs) >> 1
    for i, a := range costs[:n] {
        ans += a[0] + costs[i+n][1]
    }
    return
}

function twoCitySchedCost(costs: number[][]): number {
    costs.sort((a, b) => a[0] - a[1] - (b[0] - b[1]));
    const n = costs.length >> 1;
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        ans += costs[i][0] + costs[i + n][1];
    }
    return ans;
}

1029. 两地调度

题目描述

解法

方法一：排序 + 贪心

评论