1029.Two City Scheduling

Tags: Easy Geedy

Links: https://leetcode.com/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

---

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = costs.size(), half = n >> 1;
        sort(costs.begin(), costs.end(), [] (const vector<int> &a, const vector<int> &b) {
            return (a[0] - a[1]) < (b[0] - b[1]);
        });

        int res = 0;
        for (int i = 0; i < half; ++i) res += costs[i][0];
        for (int i = half; i < n; ++i) res += costs[i][1];

        return res;
    }
};

初看样例以为是先根据costs[i][0]排序，然后costs[i][0]相同情况下，让costs[i][1]大的在前面，很遗憾，第一个测试用例就过不去。

那么我们可以考虑如果只有两个人，记为a和b，那么需要比较的是：

a[0] + b[1]      a[1] + b[0]

假如前者小，那么：

a[0] + b[1] < a[1] + b[0]
=> a[0] - a[1] < b[0] - b[1]

所以可以根据差值来进行排序。时间复杂度$O(n \log n)$。