两地调度

难度: Medium

公司计划面试 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

Submission

运行时间: 24 ms

内存: 16.1 MB

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        sub=[x[0]-x[1] for x in costs]
        a,b=[],[]
        for each in costs:
            if each[0]<each[1]:
                a.append(each[0])
            else:
                b.append(each[1])
        curr=sum(a)+sum(b)
        m,n=len(a),len(b)
        if m<n:
            remain = [x for x in sub if x>=0]
            while m<n:
                tmp=min(remain)
                curr+=tmp
                remain.remove(tmp)
                m+=1
                n-=1
            return curr
        elif m>n:
            remain = [abs(x) for x in sub if x<0]
            while m>n:
                tmp=min(remain)
                curr+=tmp
                remain.remove(tmp)
                m-=1
                n+=1
            return curr
        else:
            return curr

Explain

此题解的思路是首先计算每个人去A市和B市的费用差，并基于此差值进行决策。首先，对于每个人，如果去A市比去B市便宜，就先选定其去A市，反之则去B市。之后，根据已选的结果检查A市和B市是否人数均为n。如果某城市人数过多，将需要重新考虑一些人的目的地，选取使总成本最小增加的方案。这通过计算差值的绝对值最小的调整来实现，以确保在调整人数以满足条件时增加的成本最小。

时间复杂度: O(n^2)

空间复杂度: O(n)

# 添加了注释的题解代码

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        # 计算每个人去A与去B的成本差
        sub = [x[0] - x[1] for x in costs]
        a, b = [], []
        # 根据成本差决定初步分配
        for each in costs:
            if each[0] < each[1]:
                a.append(each[0])
            else:
                b.append(each[1])
        # 计算当前总成本
        curr = sum(a) + sum(b)
        # 对于人数不平衡的情况进行调整
        m, n = len(a), len(b)
        if m < n:
            remain = [x for x in sub if x >= 0]
            # 调整人数至平衡
            while m < n:
                tmp = min(remain)
                curr += tmp
                remain.remove(tmp)
                m += 1
                n -= 1
            return curr
        elif m > n:
            remain = [abs(x) for x in sub if x < 0]
            while m > n:
                tmp = min(remain)
                curr += tmp
                remain.remove(tmp)
                m -= 1
                n += 1
            return curr
        else:
            return curr

Explore

在题解中，每个人去A市和去B市的成本差是通过计算'去A市的成本'与'去B市的成本'之间的差值来得到的。具体来说，对于数组中的每个元素`costs[i] = [aCosti, bCosti]`，成本差计算为`aCosti - bCosti`。这个差值反映了个人去A市相较于去B市的额外成本，如果值为正，则表示去B市更便宜；如果值为负，则表示去A市更便宜。

在初步分配后，选择进行调整的策略是基于成本差的大小，而不是直接基于个体的总成本。这是因为我们的目标是调整分配以平衡两个城市的人数，同时尽量减少总成本的增加。选择成本差较小的个体进行重新分配意味着这些个体从一个城市转移到另一个城市的额外成本较低，从而能更有效地控制总成本的增加。如果选择成本最高的个体，可能会导致总成本大幅增加，这不符合最小化总成本的目标。

题解中提出的调整策略基于最小化因调整分配而增加的额外成本，这通常可以帮助接近最小总成本的解决方案，但不一定总能保证得到全局最优解。存在可能的更优策略，如使用动态规划、贪心算法的改进版本或其他优化算法来更全面地考虑所有可能的分配方式，从而可能找到一个更低的总成本。此外，可以通过模拟退火或遗传算法等启发式算法来探索可能的更好解决方案，尤其是在问题规模较大时。