DEV Community

Subramanya Chakravarthy

Posted on

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
};
``````