Two City Scheduling

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:

1. Compute the cost of sending every person to City A

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

2. Compute the difference if a Person is sent to City B

   1. D1 -> 20 - 10 = 10
   2. D2 -> 200 - 30 = 170
   3. D3 -> 50 - 400 = -350
   4. 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

3. Sort the diff

   D3, D4, D1, D2

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

5. 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:

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

   1. D1 -> 10 - 20 = -10
   2. D2 -> 30 - 200 = -170
   3. D3 -> 400 - 50 = 350
   4. D4 -> 30 - 20 = 10

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

3. 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
};