两地调度

题目

公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为costs[i][1]

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

我的目标打造为精品的算法刷题星球，2021年最后30天，我发66张30元优惠券，平均下来一天2毛多，打卡满300天，全部退费。期待你的加入，一起努力365天，实现心中梦想，记住一切皆有可能：

示例

输入：[[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 A 市，费用为 10。
第二个人去 A 市，费用为 30。
第三个人去 B 市，费用为 50。
第四个人去 B 市，费用为 20。

最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。

来源：力扣（LeetCode）

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

补充下面代码：

class Solution(object):
    def twoCitySchedCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """

分析

如何从零开始分析这道题？如何构思？

最基本的思路：选择[ACost,BCost]成本较小的飞往对应城市，哪个城市人数先到N，剩余的人都分配另一个城市。这个思路有问题吗？考虑下面的例子：

[[10,20],[30,200],[50,400],[30,20]]

根据上述思路：

第一个应该飞往A，成本为10

第二个飞往A，成本为30

A城市率先到N人，所以剩余的都飞B城市，成本分别为400,20

总成本：10 + 30 + 400 + 20 = 460

很明显这不是最优解，因为选择400成本已有问题。

这种维度的贪心问题出在哪里？只根据元素[ACost,BCost]的两者大小选择是有问题的，上面的例子交换第二、三个元素的顺序：

[[10,20],[50,400],[30,200],[30,20]]

第一个应该飞往A，成本为10

第二个飞往A，成本为50

A城市率先到N人，所以剩余的都飞B城市，成本分别为200,20

总成本：10 + 50 + 200 + 20 = 280

同样思路，仅仅交换元素顺利，但整个问题没有变化，得到结果必须相同的才是正确的思路。

这种变化也让我们意识到，[ACost,BCost]的差值是不受列表内元素出现顺序影响的，所以取得差值绝对值：abs(ACost-BCost)，相差越大的越是应该要优先选择成本更小的。所以，对成本差的绝对值降序排序，按照此顺序，贪心的选择成本较小者飞往对应城市，哪个城市率先到N人，剩余的就都安排到另一个城市。

综上所述：维度abs(ACost-BCost)的贪心，确保取得最优解。