跳转至

两地调度

本文总阅读量次 ,原创教程,严禁转载

两地调度

题目

公司计划面试 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)的贪心 ,确保取得最优解。