leetcode1029

 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 += 1
11                 allcosts += costs[i][0]
12             else:
13                 if right < n//2:
14                     right += 1
15                     allcosts += costs[i][1]
16                 else:
17                     left += 1
18                     allcosts += costs[i][0]
19         return allcosts

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