Scale Engineer

Two City Scheduling

Med
#0983Time: O(2^(2n)). While pruning helps, the number of valid combinations is C(2n, n), which is exponential. For n=50, this is prohibitively large.Space: O(n), for the recursion stack depth, which can go up to 2n.1 company
Patterns
Greedy
Algorithms
Sorting
Data structures
Array
Companies
Swiggy

Prompt

A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.

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

 

Example 1:

Input: costs = [[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.

Example 2:

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

Example 3:

Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
Output: 3086

 

Constraints:

  • 2 * n == costs.length
  • 2 <= costs.length <= 100
  • costs.length is even.
  • 1 <= aCosti, bCosti <= 1000

Approaches

3 approaches with complexity analysis and trade-offs.

This approach explores every possible valid assignment of people to cities. We can define a recursive function that tries to assign each person to either city A or city B, while keeping track of the number of people assigned to each city. We backtrack and explore all combinations that result in exactly n people in each city and find the one with the minimum total cost.

Algorithm

  • Define a recursive function calculate(index, countA, countB) that computes the minimum cost for people from index to 2n-1.
  • The parameters countA and countB track the number of people already assigned to city A and city B, respectively.
  • Base Case: If index reaches 2n (all people assigned), check if countA == n and countB == n. If so, this is a valid assignment, and the cost from this point is 0. Otherwise, it's an invalid assignment, so return a very large value.
  • Recursive Step: For the person at index, explore two possibilities:
    1. Send to City A: If countA < n, recursively call calculate(index + 1, countA + 1, countB) and add costs[index][0].
    2. Send to City B: If countB < n, recursively call calculate(index + 1, countA, countB + 1) and add costs[index][1].
  • Return the minimum cost from the valid choices.
  • The initial call is calculate(0, 0, 0).

Walkthrough

We can model this problem as finding the minimum cost path in a decision tree. We define a recursive function, say calculate(index, countA, countB), which calculates the minimum cost for people from index to 2n-1, given that countA people have already been assigned to city A and countB to city B.

The state of our recursion is (index, countA, countB).

  • Base Case: If index reaches 2n, all people have been assigned. If countA == n and countB == n, we have a valid assignment, and the cost from this point is 0. Otherwise, it's an invalid assignment, so we return a very large value to signify this path should not be chosen.
  • Recursive Step: For the person at index, we have two choices:
    1. Send to City A: If countA < n, we can send this person to city A. The cost would be costs[index][0] + calculate(index + 1, countA + 1, countB).
    2. Send to City B: If countB < n, we can send this person to city B. The cost would be costs[index][1] + calculate(index + 1, countA, countB + 1).

We take the minimum of the costs of the available choices. The initial call to the function would be calculate(0, 0, 0). To avoid recomputing, memoization can be used, which transitions this solution to the dynamic programming approach.

class Solution {    public int twoCitySchedCost(int[][] costs) {        // Using a memoization table would optimize this to a DP solution.        // int[][][] memo = new int[costs.length][costs.length/2 + 1][costs.length/2 + 1];        return calculate(costs, 0, 0, 0);    }     private int calculate(int[][] costs, int index, int countA, int countB) {        int n = costs.length / 2;        if (index == costs.length) {            // If we have exactly n people in each city, we found a valid solution.            return 0;        }         int costToA = Integer.MAX_VALUE;        if (countA < n) {            costToA = costs[index][0] + calculate(costs, index + 1, countA + 1, countB);        }         int costToB = Integer.MAX_VALUE;        if (countB < n) {            costToB = costs[index][1] + calculate(costs, index + 1, countA, countB + 1);        }         return Math.min(costToA, costToB);    }}

Complexity

Time

O(2^(2n)). While pruning helps, the number of valid combinations is C(2n, n), which is exponential. For n=50, this is prohibitively large.

Space

O(n), for the recursion stack depth, which can go up to 2n.

Trade-offs

Pros

  • Simple to conceptualize and follows the problem statement directly.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Will result in a 'Time Limit Exceeded' error for the given constraints.

Solutions

class Solution { public int twoCitySchedCost ( int [][] costs ) { Arrays . sort ( costs , ( a , b ) -> { return a [ 0 ] - a [ 1 ] - ( b [ 0 ] - b [ 1 ]); }); int ans = 0 ; int n = costs . length >> 1 ; for ( int i = 0 ; i < n ; ++ i ) { ans += costs [ i ][ 0 ] + costs [ i + n ][ 1 ]; } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem