Course4all

Two City Scheduling

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Greedy.

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 ithi^{th} person to city A is aCost_i, and the cost of flying the ithi^{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 NN people to City A and NN people to City B. This results in (2NN)\binom{2N}{N} combinations.

Thought Process

  1. solve(idx, countA, countB): Assign person idx.
  2. Option 1: Assign to A (if countA < n).
  3. Option 2: Assign to B (if countB < n).
  4. 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

  1. dp[i][j] = min cost for i in A and j in B.
  2. Transition: dp[i][j] = min(dp[i-1][j] + costA, dp[i][j-1] + costB).
  3. 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 NN 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−bCostaCost - bCost.

Thought Process

  1. Assume everyone goes to B initially (Total = ∑bCost\sum bCost).
  2. The 'refund' we get by moving person ii to A instead of B is (bCosti−aCosti)(bCost_i - aCost_i), or conversely, the 'extra cost' is (aCosti−bCosti)(aCost_i - bCost_i).
  3. Sort all people by (aCosti−bCosti)(aCost_i - bCost_i).
  4. Pick the first NN 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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionCourse Schedule III
Next Question →Hand of Straights