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.
```

The question is a bit tricky, with only one test case

**Algorithm:**

#### Approach 1:

Compute the cost of sending every person to City A

The cost will be 10 + 30 + 400 + 30 = 470

Compute the difference if a Person is sent to City B

- D1 -> 20 - 10 = 10
- D2 -> 200 - 30 = 170
- D3 -> 50 - 400 = -350
- D4 -> 20 - 30 = -10

If the last two persons are sent to City B instead of City A, you can save maximum, as those are the persons costing more to City A

Sort the diff

D3, D4, D1, D2

Now pick N persons which has least diff and send them to City B

Add the diff cost to the total

470 + (-350) + -(10) = 110

## Code

```
/**
* @param {number[][]} costs
* @return {number}
*/
var twoCitySchedCost = function(costs) {
let res = 0
let diff = new Array()
for (let i = 0; i < costs.length; i++) {
res += costs[i][0]
diff.push(costs[i][1] - costs[i][0])
}
diff.sort((a, b) => a - b)
for (let i = 0; i < costs.length / 2; i++) {
res += diff[i]
}
return res
};
```

## Approach 2:

The intuition is to send maximum saving to City A and rest of them to city B

- D1 -> 10 - 20 = -10
- D2 -> 30 - 200 = -170
- D3 -> 400 - 50 = 350
- D4 -> 30 - 20 = 10

Sort the arrays based on the difference cost between city A and city B

Send first N persons to City A and the next N to city B

## Code:

```
/**
* @param {number[][]} costs
* @return {number}
*/
var twoCitySchedCost = function(costs) {
costs.sort((p1, p2) => (p1[0] - p2[0]) - (p1[1] - p2[1]))
let res = 0;
let N = costs.length / 2;
for (let i = 0; i < N; i++) {
res += costs[i][0]
res += costs[N + i][1]
}
return res
};
```