Two City Scheduling

This question is asked by Google. A company is booking flights to send its employees to its two satellite offices A and B. The cost of sending the ith employee to office A and office B is given by prices[i][0] and prices[i][1] respectively. Given that half the employees must be sent to office A and half the employees must be sent to office B, return the minimum cost the company must pay for all their employees' flights.

Example(s)

Example 1:

Input: prices = [[40, 30], [300, 200], [50, 50], [30, 60]]
Output: 310
Explanation:
Send employee 0 to office B: cost 30
Send employee 1 to office B: cost 200
Send employee 2 to office A: cost 50
Send employee 3 to office A: cost 30
Total: 30 + 200 + 50 + 30 = 310

Office A: 2 employees (employees 2, 3)
Office B: 2 employees (employees 0, 1)

Example 2:

Input: prices = [[10, 20], [30, 200], [400, 50], [30, 20]]
Output: 110
Explanation:
Send employee 0 to office A: cost 10
Send employee 1 to office A: cost 30
Send employee 2 to office B: cost 50
Send employee 3 to office A: cost 30
Wait, that's 3 to A and 1 to B, not balanced.

Actually:
Send employee 0 to office A: cost 10
Send employee 1 to office A: cost 30
Send employee 2 to office B: cost 50
Send employee 3 to office B: cost 20
Total: 10 + 30 + 50 + 20 = 110

Office A: 2 employees (employees 0, 1)
Office B: 2 employees (employees 2, 3)

Example 3:

Input: prices = [[259, 770], [448, 54], [926, 667], [184, 139], [840, 118], [577, 469]]
Output: 1859
Explanation:
Optimal assignment minimizes total cost while sending exactly half to each office.

Solution

The solution uses Dynamic Programming:

DP state: dp[i][j] = minimum cost to assign first i employees with j employees sent to office A
Base case: dp[0][0] = 0 (no employees, no cost)
Recurrence: For each employee, choose office A or B
Result: dp[n][n/2] where n is number of employees

JavaScript Solution
Python Solution

JavaScript Solution - Dynamic Programming

/**
* Find minimum cost to send half employees to each office
* @param {number[][]} prices - prices[i][0] = cost to A, prices[i][1] = cost to B
* @return {number} - Minimum total cost
*/
function twoCityScheduling(prices) {
const n = prices.length;
const half = n / 2;

// dp[i][j] = minimum cost to assign first i employees with j employees sent to office A
const dp = Array(n + 1).fill().map(() => Array(half + 1).fill(Infinity));

// Base case: no employees, no cost
dp[0][0] = 0;

// Fill DP table
for (let i = 1; i <= n; i++) {
  for (let j = 0; j <= Math.min(i, half); j++) {
    // Option 1: Send employee i-1 to office A
    if (j > 0) {
      dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + prices[i - 1][0]);
    }
    
    // Option 2: Send employee i-1 to office B
    // Number sent to B = (i - 1) - (j) = i - 1 - j
    // We need at most half to B, so i - 1 - j <= half
    if (i - 1 - j < half) {
      dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + prices[i - 1][1]);
    }
  }
}

return dp[n][half];
}

// Test cases
console.log('Example 1:', twoCityScheduling([[40, 30], [300, 200], [50, 50], [30, 60]])); 
// 310

console.log('Example 2:', twoCityScheduling([[10, 20], [30, 200], [400, 50], [30, 20]])); 
// 110

Output:

Click "Run Code" to execute the code and see the results.

Python Solution - Dynamic Programming

from typing import List

def two_city_scheduling(prices: List[List[int]]) -> int:
  """
  Find minimum cost to send half employees to each office
  
  Args:
      prices: prices[i][0] = cost to A, prices[i][1] = cost to B
      
  Returns:
      int: Minimum total cost
  """
  n = len(prices)
  half = n // 2
  
  # dp[i][j] = minimum cost to assign first i employees with j employees sent to office A
  dp = [[float('inf')] * (half + 1) for _ in range(n + 1)]
  
  # Base case: no employees, no cost
  dp[0][0] = 0
  
  # Fill DP table
  for i in range(1, n + 1):
      for j in range(min(i, half) + 1):
          # Option 1: Send employee i-1 to office A
          if j > 0:
              dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + prices[i - 1][0])
          
          # Option 2: Send employee i-1 to office B
          # Number sent to B = (i - 1) - j
          # We need at most half to B, so i - 1 - j < half
          if i - 1 - j < half:
              dp[i][j] = min(dp[i][j], dp[i - 1][j] + prices[i - 1][1])
  
  return dp[n][half]

# Test cases
print('Example 1:', two_city_scheduling([[40, 30], [300, 200], [50, 50], [30, 60]]))  
# 310

print('Example 2:', two_city_scheduling([[10, 20], [30, 200], [400, 50], [30, 20]]))  
# 110

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Greedy with Sorting)

Here's a greedy solution that can be more intuitive:

JavaScript Greedy
Python Greedy

/**
 * Greedy solution: Sort by cost difference
 * Send employees with largest savings to their cheaper office first
 */
function twoCitySchedulingGreedy(prices) {
  const n = prices.length;
  const half = n / 2;
  
  // Sort by cost difference (savings of sending to A vs B)
  // Negative difference means A is cheaper, positive means B is cheaper
  const sorted = prices.map((p, i) => ({
    index: i,
    diff: p[0] - p[1], // A cost - B cost
    priceA: p[0],
    priceB: p[1]
  })).sort((a, b) => a.diff - b.diff);
  
  let total = 0;
  let countA = 0;
  
  // First half: send to A (where A is relatively cheaper)
  for (let i = 0; i < half; i++) {
    total += sorted[i].priceA;
    countA++;
  }
  
  // Second half: send to B (where B is relatively cheaper)
  for (let i = half; i < n; i++) {
    total += sorted[i].priceB;
  }
  
  return total;
}

def two_city_scheduling_greedy(prices: List[List[int]]) -> int:
    """
    Greedy solution: Sort by cost difference
    Send employees with largest savings to their cheaper office first
    """
    n = len(prices)
    half = n // 2
    
    # Sort by cost difference (A cost - B cost)
    # Negative means A is cheaper, positive means B is cheaper
    sorted_prices = sorted(prices, key=lambda p: p[0] - p[1])
    
    total = 0
    
    # First half: send to A (where A is relatively cheaper)
    for i in range(half):
        total += sorted_prices[i][0]
    
    # Second half: send to B (where B is relatively cheaper)
    for i in range(half, n):
        total += sorted_prices[i][1]
    
    return total

Complexity

Time Complexity:
- DP: O(n²) - Where n is the number of employees. We fill a DP table of size n × (n/2).
- Greedy: O(n log n) - Sorting the prices array.
Space Complexity:
- DP: O(n²) - For the DP table.
- Greedy: O(n) - For sorting (or O(1) if sorted in-place).

Approach

The solution uses Dynamic Programming:

DP state:
- dp[i][j] = minimum cost to assign first i employees with j employees sent to office A
- We track how many have been sent to A (must be exactly n/2 at the end)
Base case:
- dp[0][0] = 0 - No employees, no cost
Recurrence:
- For employee i-1, we have two choices:
  - Send to A: dp[i][j] = dp[i-1][j-1] + prices[i-1][0] (if j > 0)
  - Send to B: dp[i][j] = dp[i-1][j] + prices[i-1][1] (if we haven't sent too many to B)
- Take the minimum of both options
Result:
- dp[n][n/2] = minimum cost with exactly n/2 employees sent to A

Key Insights

Dynamic Programming: Optimal substructure - optimal assignment uses optimal subproblems
Constraint: Exactly half to each office
Two choices: For each employee, send to A or B
O(n²) time: Must consider all assignments
Greedy alternative: Sort by cost difference for O(n log n) solution

Step-by-Step Example

Let's trace through Example 1: prices = [[40, 30], [300, 200], [50, 50], [30, 60]]

prices = [[40, 30], [300, 200], [50, 50], [30, 60]]
n = 4, half = 2

DP table (dp[i][j]): j = number sent to A
        j:  0  1  2
  i=0:      0  ∞  ∞
  i=1:      ?  ?  ?
  i=2:      ?  ?  ?
  i=3:      ?  ?  ?
  i=4:      ?  ?  ?

Fill table:
  i=1, j=0: Send employee 0 to B
    dp[1][0] = dp[0][0] + prices[0][1] = 0 + 30 = 30
  
  i=1, j=1: Send employee 0 to A
    dp[1][1] = dp[0][0] + prices[0][0] = 0 + 40 = 40
  
  i=2, j=0: Send employee 1 to B (employee 0 already to B)
    dp[2][0] = dp[1][0] + prices[1][1] = 30 + 200 = 230
  
  i=2, j=1: Send employee 1 to A or B
    Option 1: Send to A: dp[1][0] + prices[1][0] = 30 + 300 = 330
    Option 2: Send to B: dp[1][1] + prices[1][1] = 40 + 200 = 240
    dp[2][1] = min(330, 240) = 240
  
  i=2, j=2: Send employee 1 to A (employee 0 to A)
    dp[2][2] = dp[1][1] + prices[1][0] = 40 + 300 = 340
  
  ... (continue for i=3, 4)
  
  Final: dp[4][2] = 310

Optimal assignment:
  Employee 0 → B (30)
  Employee 1 → B (200)
  Employee 2 → A (50)
  Employee 3 → A (30)
  Total: 310

Visual Representation

Example 1: prices = [[40, 30], [300, 200], [50, 50], [30, 60]]

Employees:
  E0: A=40,  B=30  (B is cheaper, save 10)
  E1: A=300, B=200 (B is cheaper, save 100)
  E2: A=50,  B=50  (same cost)
  E3: A=30,  B=60  (A is cheaper, save 30)

Greedy approach (sort by A-B difference):
  E1: diff = 300-200 = 100  (B much cheaper)
  E3: diff = 30-60 = -30    (A cheaper)
  E0: diff = 40-30 = 10     (B slightly cheaper)
  E2: diff = 50-50 = 0      (same)

Sorted: [E3(-30), E2(0), E0(10), E1(100)]

First half to A: E3, E2 → 30 + 50 = 80
Second half to B: E0, E1 → 30 + 200 = 230
Total: 310 ✓

DP approach finds same result.

Edge Cases

Two employees: Send cheaper to each office
All same cost: Any assignment works
One office always cheaper: Still need to send half to each
Large differences: DP handles correctly
Even number required: Problem assumes even n

Important Notes

Exactly half: Must send exactly n/2 to each office
Two choices: For each employee, send to A or B
Minimize cost: Goal is minimum total cost
O(n²) time: DP must consider all assignments
Greedy alternative: Can use sorting for O(n log n)

Why Dynamic Programming Works

Optimal Substructure:

To assign first i employees optimally with j to A, we need:
- Optimal assignment of first i-1 employees
- Then decide where to send employee i-1
The optimal solution uses optimal solutions to subproblems

Overlapping Subproblems:

Multiple assignments may share the same subproblems
DP stores and reuses these optimal values

Why Greedy Works

Key insight:

Sort employees by cost difference (A - B)
Negative difference: A is cheaper, prefer sending to A
Positive difference: B is cheaper, prefer sending to B
First half (most negative) go to A, second half (most positive) go to B
This maximizes savings while maintaining balance

Partition Equal Subset Sum: Similar constraint problem
0/1 Knapsack: Similar DP structure
Assign Cookies: Different greedy problem
Meeting Rooms: Different scheduling problem

Takeaways

Dynamic Programming solves this efficiently
Constraint: Exactly half to each office
Two choices per employee: A or B
O(n²) time for DP, O(n log n) for greedy
Classic DP problem with practical applications

Example(s)​

Solution​

JavaScript Solution - Dynamic Programming

Output:

Python Solution - Dynamic Programming

Output:

Alternative Solution (Greedy with Sorting)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Edge Cases​

Important Notes​

Why Dynamic Programming Works​

Why Greedy Works​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (Greedy with Sorting)

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Edge Cases

Important Notes

Why Dynamic Programming Works

Why Greedy Works

Related Problems

Takeaways