There are 2N people a company is planning to interview. The cost of flying the ith person to city A is costs[i][0], and the cost of flying the ith 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
};
Top comments (0)