[LeetCode] 1029. Two City Scheduling

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 <= costs.length <= 100
It is guaranteed that costs.length is even.
1 <= costs[i][0], costs[i][1] <= 1000

两地调度。

公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为 costs[i][1]。

返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-city-scheduling
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是贪心，我这里直接翻译一下LC discussion的最高票答案好了，同时参考题干中的例子。

costs = [[10,20],[30,200],[400,50],[30,20]]

首先假设，如果把所有的人都安排去A地参加面试，那么会得到cost = 10 + 30 + 400 + 30 = 470。但是因为题目要求需要送一半的人去B地面试，那么现在需要选择送什么人去B地呢？可以这样想，既然我目前已经花了470块送所有人去A地面试，那么我每送一个人去B地我都算是赚到了，因为我会得到来自A地的退款。按照这个思路，应该是去检查如何安排才能使退款更多。计算退款refund的方式是

refund[i] = cost[i][1] - cost[i][0]

得到数组refund = [10, 170, -350, -10]

这里每个数字，如果是正数则说明我们需要额外付钱，如果是负数说明可以得到退款。

接下来对refund数组排序，得到refund = [-350, -10, 10, 170]，如果按照这个逻辑去安排，则最小花费是一开始的470 - 350 - 10 = 110块。

时间O(nlogn) - sort

空间O(n)

Java实现

 1 class Solution {
 2     public int twoCitySchedCost(int[][] costs) {
 3         int N = costs.length / 2;
 4         int[] refund = new int[N * 2];
 5         int minCost = 0;
 6         int index = 0;
 7         for (int[] cost : costs) {
 8             refund[index++] = cost[1] - cost[0];
 9             minCost += cost[0];
10         }
11         Arrays.sort(refund);
12         for (int i = 0; i < N; i++) {
13             minCost += refund[i];
14         }
15         return minCost;
16     }
17 }

LeetCode 题目总结