1 class Solution(object): 2     def twoCitySchedCost(self, costs: 'List[List[int]]') -> int: 3         costs = sorted(costs,key = lambda x: abs(x[0]-x[1]),reverse=True) 4         n = len(costs) 5         allcosts = 0 6         left = 0 7         right = 0 8         for i in range(n): 9             if costs[i][0] <= costs[i][1] and left < n//2:10                 left += 111                 allcosts += costs[i][0]12             else:13                 if right < n//2:14                     right += 115                     allcosts += costs[i][1]16                 else:17                     left += 118                     allcosts += costs[i][0]19         return allcosts

贪心思想：根据人距离A，B城市的费用的“差值”，从大到小排序。排的靠前的优先选择其费用低的城市。如果某个城市的人数已经达到1/2，则剩下的全部选择另外一个城市。这种方式的总体的费用最低。