Two City Scheduling

https://leetcode.com/contest/weekly-contest-133/problems/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;
    }
};