Two City Scheduling

Medium
342.

Two City Scheduling

Two City Scheduling is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google, Adobe and Bloomberg interviews.

A company is interviewing 2n people. Flying person i to city A costs costs[i][0], and flying them to city B costs costs[i][1].

Return the minimum total cost of flying exactly n people to each city.

Example 1

Input
costs = [[10,20],[30,200],[400,50],[30,20]]
Output
110
Explanation
Send the first two to A and the last two to B.

Example 2

Input
costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output
1859

Example 3

Input
costs = [[10,20],[20,10]]
Output
20

Constraints

  • 2 <= costs.length <= 40
  • costs.length is even.
  • 1 <= costs[i][0], costs[i][1] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} costs
 * @return {number}
 */
var twoCitySchedCost = function(costs) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Two City Scheduling — Solution in Python, Java & C++

Two City Scheduling solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Two City Scheduling is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google, Adobe and Bloomberg interviews.

Problem statement

A company is interviewing 2n people. Flying person i to city A costs costs[i][0], and flying them to city B costs costs[i][1].

Return the minimum total cost of flying exactly n people to each city.

Example 1

Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: Send the first two to A and the last two to B.

Example 2

Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859

Example 3

Input: costs = [[10,20],[20,10]]
Output: 20

Constraints

  • 2 <= costs.length <= 40
  • costs.length is even.
  • 1 <= costs[i][0], costs[i][1] <= 1000

Hints for Two City Scheduling

  1. Hint 1

    Imagine flying everyone to B first, then upgrading exactly n of them to A.

  2. Hint 2

    The cost of upgrading person i is costs[i][0] - costs[i][1], so upgrade the n cheapest.

  3. Hint 3

    Sorting by that difference and splitting the list in half does exactly that.

How to solve Two City Scheduling

Send everyone to B, then upgrade the n people whose A-minus-B difference is smallest (most negative). Sorting by that difference and splitting in half does it.

Approach

  1. Sort by costA - costB.
  2. Sum costA for the first half and costB for the second half.

Why it works

Exactly n must go to A, so the choice is which n. Relative to an all-B baseline, sending person i to A changes the total by costA - costB; choosing the n smallest deltas minimises the total.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Picking each person's cheaper city independently ignores the exactly-n constraint.

Reference solution

Python

def twoCitySchedCost(costs) -> int:
    ordered = sorted(costs, key=lambda c: c[0] - c[1])
    half = len(ordered) // 2
    return sum(c[0] for c in ordered[:half]) + sum(c[1] for c in ordered[half:])

Java

public static int twoCitySchedCost(int[][] costs) {
    int[][] s = costs.clone();
    Arrays.sort(s, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
    int half = s.length / 2;
    int total = 0;
    for (int i = 0; i < s.length; i++) total += i < half ? s[i][0] : s[i][1];
    return total;
}

C++

int twoCitySchedCost(vector<vector<int>>& costs) {
    vector<vector<int>> s = costs;
    sort(s.begin(), s.end(), [](const vector<int>& a, const vector<int>& b) {
        return (a[0] - a[1]) < (b[0] - b[1]);
    });
    int half = (int) s.size() / 2;
    int total = 0;
    for (int i = 0; i < (int) s.size(); i++) total += i < half ? s[i][0] : s[i][1];
    return total;
}

JavaScript

var twoCitySchedCost = function(costs) {
    const sorted = costs.slice().sort(function(a, b) { return (a[0] - a[1]) - (b[0] - b[1]); });
    const half = sorted.length / 2;
    let total = 0;
    for (let i = 0; i < sorted.length; i++) {
        total += i < half ? sorted[i][0] : sorted[i][1];
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms