1029. Two City Scheduling

Loading...LeetCode

一点都不easy啊...竟然是这样greedy出来的，让我想起比较优势理论 Comparative advantage。

12/27/2020 Update:

也可以用DP做，但这题没法记忆，会TLE。Try to assign a person to both cities if its possible (a typical DP technique) and return the minimum of it.

Greedy

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

DP

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        n = len(costs)//2
        
        def dp(idx, countA):
            if countA > n:
                return float('inf')
            if idx == len(costs):
                if countA == n:
                    return 0
                else:
                    return float('inf')
            return min(costs[idx][0]+dp(idx+1, countA+1),
                      costs[idx][1]+dp(idx+1, countA))
        
        return dp(0, 0)