Q1029-两地调度-中等-贪心

1029. 两地调度

Question

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

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

Example 1:

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

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

Note:

• 1 <= costs.length <= 100
• costs.length 为偶数
• 1 <= costs[i][0], costs[i][1] <= 1000

Apporach 1: 贪心

我们这样来看这个问题，公司首先将这 2N 个人全都安排飞往 B 市，再选出 N 个人改变它们的行程，让他们飞往 A 市。如果选择改变一个人的行程，那么公司将会额外付出 price_A - price_B 的费用，这个费用可正可负。

因此最优的方案是，选出 price_A - price_B 最小的 N 个人，让他们飞往 A 市，其余人飞往 B 市。

算法

• 按照 price_A - price_B 从小到大排序；
• 将前 N 个人飞往 A 市，其余人飞往 B 市，并计算出总费用。

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        # Sort by a gain which company has
        # by sending a person to city A and not to city B
        costs.sort(key = lambda x : x[0] - x[1])

        total = 0
        n = len(costs) // 2
        # To optimize the company expenses,
        # send the first n persons to the city A
        # and the others to the city B
        for i in range(n):
            total += costs[i][0] + costs[i + n][1]
        return total

Or

class Solution:
    def twoCitySchedCost(self, costs) -> int:
        N=len(costs)
        deltacost=[]
        COSTAB=0
        for i in range(N):# 改派i去A城，花费变动deltacost[i]
            deltacost.append(costs[i][0]-costs[i][1])
            COSTAB=COSTAB+costs[i][1]
        deltacost=sorted(deltacost)
        for i in range(round(N/2)):
            COSTAB=COSTAB+deltacost[i]
        return COSTAB

复杂度分析

• 时间复杂度：，需要对 price_A - price_B 进行排序。
• 空间复杂度：。