# 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)`

.

### Did you find this article valuable?

Support **Nhut Nguyen** by becoming a sponsor. Any amount is appreciated!