# 1029. Two City Scheduling 两地调度

@TOC

## # 题目描述

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.

Example 1:

``````Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation:
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
``````

Note:

1. `1 <= costs.length <= 100`
2. `It is guaranteed that costs.length is even.`
3. `1 <= costs[i][0], costs[i][1] <= 1000`

## # 解题方法

### # 小根堆

B-A+20+170-350-10

``````class Solution(object):
def twoCitySchedCost(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
heap = []
for i, cost in enumerate(costs):
heapq.heappush(heap, (cost[1] - cost[0], i))
res = 0
count = 0
while heap:
cost, pos = heapq.heappop(heap)
if count < len(costs) / 2:
res += costs[pos][1]
else:
res += costs[pos][0]
count += 1
return res
``````

### # 排序

``````class Solution(object):
def twoCitySchedCost(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
_len = len(costs)
cost_diff = []
for i, cost in enumerate(costs):
cost_diff.append((cost[1] - cost[0], i))
cost_diff.sort()
res = 0
count = 0
for i, (diff, pos) in enumerate(cost_diff):
if i < _len / 2:
res += costs[pos][1]
else:
res += costs[pos][0]
return res
``````

## # 日期

2019 年 8 月 31 日 —— 赶在月底做个题