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

## Thoughts

假设A取的都是first, 那么A是想取first和sec中尽量都是first小的，也就是每个单独能max(sec - first)的。同理B是想取max(f - s), 也就是min(sec - first）。因此对first-sec排序，前一半归A, 后一半归B. a\[0] - a\[1] < b\[0] - b\[1] => a\[0] + b\[1] < a\[1] + b\[0] 意味着a去0b去1比a去1比b去0好。当有多个元素时，前一半去A后一半去B比任意调换其中顺序的结果好。

```
class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(), costs.end(), [](vector<int>& a, vector<int>& b) {
            return a[0] - a[1] < b[0] - b[1];
        });
        int cost = 0;
        for (int i = 0; i < costs.size(); ++i) {
            cost += i < costs.size() / 2 ? costs[i][0] : costs[i][1]; 
        }
        return cost;
    }
};
```