题目
There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].
Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.
解题思路
先让所有人去A城市，让第i个人去B城市的额外花销是costs[i][1] - costs[i][0]，使用优先队列找出额外花销最小的n个人，让他们去B城市
代码
import heapq
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
n = len(costs) // 2
res = 0
q = []
for i in range(n):
res += costs[i][0]
heapq.heappush(q, costs[i][1] - costs[i][0])
for i in range(n, 2 * n):
res += costs[i][0]
res += heapq.heappushpop(q, costs[i][1] - costs[i][0])
return res
