Problem statement

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

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.
Explanation: 1859 = 259 + 54 + 667 + 184 + 118 + 577.

Example 3

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

Constraints

• 2 * n == costs.length.
• 2 <= costs.length <= 100.
• costs.length is even.
• 1 <= aCost_i, bCost_i <= 1000.

Solution: Switching flight with least sacrifice

Every candidate should fly to the city with a lower cost. But the problem requires they must share their appearance equally between the two cities. It means somebody might have to fly with a higher cost.

Because the company considers only the total cost sum, you should choose the ones that sacrifice minimal cost for their flight to make them happy to switch.

Example 2

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

• If everyone can fly with a lower cost, only the first person flies to city a, the others fly to city b.
• But with the problem's constraint, some have to fly to city a. The ones that have the least sacrifices in cost are the fourth one (184 - 139 = 45) and the last one (577 - 469 = 108). You can say the company only has to pay 45 + 108 = 153 (dollars) more for its optimal scheduling.
• The final cost is 259 + 54 + 667 + 184 + 118 + 577 = 1859.

How to implement the idea

You can generalize the idea of sacrifice for all candidates.

For instance in Example 2, you might say the first one "sacrifices" 259 - 770 = -511 (dollars) as well because you will choose the ones with the least sacrifices anyway.

Code

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int twoCitySchedCost(vector<vector<int>>& costs) {
    // sort on the sacrifices in cost
    sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b){
        return a[0] - a[1] < b[0] - b[1];
    });
    int cost = 0;
    for (int i = 0; i < costs.size() / 2; i++) { // first n person 
        cost += costs[i][0];
    }
    for (int i = costs.size() / 2; i < costs.size(); i++) {
        cost += costs[i][1];
    }
    return cost;
}
int main() {
    vector<vector<int>> costs{{10,20},{30,200},{400,50},{30,20}};
    cout << twoCitySchedCost(costs) << endl;
    costs = {{259,770},{448,54},{926,667},{184,139},{840,118},{577,469}};
    cout << twoCitySchedCost(costs) << endl;
}

Output:
110
1859

Complexity

• Runtime: O(NlogN), where N = costs.length.
• Extra space: O(1).