DEV Community

Subramanya Chakravarthy
Subramanya Chakravarthy

Posted on

2 2

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

Image of Datadog

Measure and Advance Your DevSecOps Maturity

In this white paper, we lay out a DevSecOps maturity model based on our experience helping thousands of organizations advance their DevSecOps practices. Learn the key competencies and practices across four distinct levels of maturity.

Get The White Paper

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more