Leetcode 1029: Two city Scheduling

A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.

Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.

Example 1:

Input: costs = [[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.

Example 2:

Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859

Example 3:

Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
Output: 3086

Constraints:

• 2 * n == costs.length
• 2 <= costs.length <= 100
• costs.length is even.
• 1 <= aCosti, bCosti <= 1000

Problem Analysis:

If we iterate all possibilities, we get the time complexity O(n!). It’s terrible.

We need to separate 2n people into two parts and make the costs are minimum.

Assume we have select n people into a part, so the other n people into another part. We can compute the current cost. If we switch ith people in one part and jth people in another part, so after switching, the cost is smaller. We simply get the formula is cost_after = cost_before + (costs[i][1]-costs[i][0])+(costs[j][0]-costs[j][1]).

Here we assume diff(i) = costs[i][1]-costs[i][0]. So there is a tricky way to get the minimum cost. First we compute the cost that select 2n people all flying to city a. Then we compute all diffs, we then add n smallest diffs that it means makeing the n people flying to city b. We can simply know that this cost is minimum cost.

Solution

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        vector<int> refund;
        int res{0};
        for (const auto& item : costs) {
            res += item[0];
            refund.push_back(item[1] - item[0]);
        }
        sort(begin(refund), end(refund));
        res += accumulate(begin(refund), refund.begin() + refund.size() / 2, 0);

        return res;
    }
};

Time complexity is O(nlgn)

Space complexity is O(n)