Two City Scheduling

Master this topic with zero to advance depth.

Two City Scheduling

A company is planning to interview 2n people. Given the array costs where costs[i] = [aCost_i, bCost_i], the cost of flying the $i^{th}$ person to city A is aCost_i, and the cost of flying the $i^{th}$ person to city B is bCost_i.

Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.

Visual Representation

Costs: [[10, 20], [30, 200], [400, 50], [30, 20]]

Profit of picking A over B (a - b):
1. 10 - 20  = -10
2. 30 - 200 = -170 (Huge saving if A)
3. 400 - 50 = +350 (Huge saving if B)
4. 30 - 20  = +10

Sorted diffs: -170, -10, +10, +350
Pick first 2 for A, last 2 for B.

Medium

Examples

Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Fly person 1 and 2 to city A, and person 3 and 4 to city B.

Approach 1

Level I: Recursive Backtracking

Intuition

Try every possible way to assign $N$ people to City A and $N$ people to City B. This results in $\binom{2N}{N}$ combinations.

Thought Process

solve(idx, countA, countB): Assign person idx.
Option 1: Assign to A (if countA < n).
Option 2: Assign to B (if countB < n).
Return minimum total cost from both paths.

Pattern: Brute Force / Combinations

⏱ O(2^{2N}) or more accurately O(\binom{2N}{N}).💾 O(N) for recursion.

Detailed Dry Run

[[10,20], [30,200]]

A(10) then B(200) = 210
B(20) then A(30) = 50 Min = 50.

java

public class Solution {
    public int twoCitySchedCost(int[][] costs) {
        return solve(0, 0, 0, costs.length / 2, costs, new HashMap<>());
    }
    private int solve(int i, int a, int b, int n, int[][] costs, Map<String, Integer> memo) {
        if (i == costs.length) return 0;
        String key = i + "," + a;
        if (memo.containsKey(key)) return memo.get(key);
        int res = Integer.MAX_VALUE;
        if (a < n) res = Math.min(res, costs[i][0] + solve(i + 1, a + 1, b, n, costs, memo));
        if (b < n) res = Math.min(res, costs[i][1] + solve(i + 1, a, b + 1, n, costs, memo));
        memo.put(key, res);
        return res;
    }
}

Approach 2

Level II: Dynamic Programming

Intuition

This is a classic 2D DP problem. dp[i][j] represents the minimum cost for the first i+j people, with i people assigned to City A and j people assigned to City B.

Thought Process

dp[i][j] = min cost for i in A and j in B.
Transition: dp[i][j] = min(dp[i-1][j] + costA, dp[i][j-1] + costB).
Base case: dp[0][0] = 0.

Pattern: 2D Dynamic Programming

⏱ O(N^2).💾 O(N^2) or O(N) using space optimization.

Detailed Dry Run

[[10,20], [30,200], [400,50], [30,20]] dp[1][0] = 10, dp[0][1] = 20 dp[1][1] = min(10+200, 20+30) = 50 dp[2][0] = 10+30 = 40 (N=2) ...

java

public class Solution {
    public int twoCitySchedCost(int[][] costs) {
        int n = costs.length / 2;
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i - 1][0] + costs[i - 1][0];
            dp[0][i] = dp[0][i - 1] + costs[i - 1][1];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] + costs[i + j - 1][0], 
                                    dp[i][j - 1] + costs[i + j - 1][1]);
            }
        }
        return dp[n][n];
    }
}

Approach 3

Level III: Optimal Greedy (Sorting by Relative Cost)

Intuition

Imagine we send everyone to City B first. Now we need to pick $N$ people to 'swap' to City A. To minimize total cost, we should pick the people for whom the cost reduction (or least increase) of moving to A is greatest. This is $aCost - bCost$ .

Thought Process

Assume everyone goes to B initially (Total = $\sum bCost$ ).
The 'refund' we get by moving person $i$ to A instead of B is $(bCost_i - aCost_i)$ , or conversely, the 'extra cost' is $(aCost_i - bCost_i)$ .
Sort all people by $(aCost_i - bCost_i)$ .
Pick the first $N$ people (those with the most negative or smallest diffs) and send them to A.

Pattern: Greedy Difference Sorting

⏱ O(N log N) for sorting.💾 O(1) or O(N) depending on sort.

Detailed Dry Run

Costs: [[10,20], [30,200], [400,50], [30,20]] Diffs (A-B): [-10, -170, 350, 10] Sorted by diff: [-170, -10, 10, 350] People: [30,200], [10,20] -> Go to A. [30,20], [400,50] -> Go to B. Total: 30 + 10 + 20 + 50 = 110.

java

import java.util.*;

public class Solution {
    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
        int total = 0, n = costs.length / 2;
        for (int i = 0; i < n; i++) total += costs[i][0]; // First n go to A
        for (int i = n; i < costs.length; i++) total += costs[i][1]; // Last n go to B
        return total;
    }
}

← Previous QuestionCourse Schedule III

Next Question →Hand of Straights

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.