# Two City Scheduling
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/two-city-scheduling)
Canonical: https://scaleengineer.com/dsa/problems/two-city-scheduling
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Swiggy](https://scaleengineer.com/companies/swiggy)
---
## Problem
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
## Brute Force using Recursion
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.
**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.
**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.
### Explanation
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.
```java
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);
    }
}
```
### 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)`.

## Dynamic Programming
A more optimized approach is to use dynamic programming to avoid re-computing results for the same subproblems. We can define a DP state `dp[i][j]` as the minimum cost to assign the first `i` people such that `j` of them are sent to city A. The final answer would be the state where all `2n` people are assigned, with `n` in city A.
**Time:** O(n^2), as we iterate through a DP table of size approximately 2n * n. · **Space:** O(n^2) for the DP table. This can be optimized to O(n) since each state `dp[i]` only depends on the previous state `dp[i-1]`.
**Pros:** Guarantees an optimal solution.; Much more efficient than brute force and passes within time limits.
**Cons:** Slightly more complex to implement than the greedy approach.; Not as efficient as the greedy solution in terms of time complexity.
### Explanation
This approach uses dynamic programming to solve the problem by breaking it down into smaller, overlapping subproblems. We define `dp[i][j]` as the minimum cost to schedule the first `i` people, with exactly `j` of them assigned to city A. Consequently, `i-j` people are assigned to city B.

The state transition is as follows: To compute `dp[i][j]`, we consider the `i`-th person (at index `i-1` in the `costs` array). This person can be assigned to either city A or city B.
1.  **Assign person `i-1` to City A:** This is possible if we have `j-1` people assigned to city A among the first `i-1` people. The cost would be `dp[i-1][j-1] + costs[i-1][0]`. This choice is valid only if `j > 0`.
2.  **Assign person `i-1` to City B:** This is possible if we have `j` people assigned to city A among the first `i-1` people. The cost would be `dp[i-1][j] + costs[i-1][1]`. This choice is valid only if the number of people in city B, `i-j`, does not exceed `n`.

The value of `dp[i][j]` is the minimum of these two options. The DP table is of size `(2n+1) x (n+1)`. The base case is `dp[0][0] = 0`. The final answer is `dp[2n][n]`.
```java
class Solution {
    public int twoCitySchedCost(int[][] costs) {
        int n = costs.length / 2;
        int[][] dp = new int[2 * n + 1][n + 1];

        for (int i = 0; i <= 2 * n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = Integer.MAX_VALUE / 2;
            }
        }
        dp[0][0] = 0;

        for (int i = 1; i <= 2 * n; i++) {
            for (int j = 0; j <= n; j++) {
                // Option 1: Person i-1 goes to city A
                int costA = Integer.MAX_VALUE / 2;
                if (j > 0) {
                    costA = dp[i - 1][j - 1] + costs[i - 1][0];
                }

                // Option 2: Person i-1 goes to city B
                int costB = Integer.MAX_VALUE / 2;
                if (i - j <= n) { // Number of people in city B must not exceed n
                    costB = dp[i - 1][j] + costs[i - 1][1];
                }
                
                dp[i][j] = Math.min(costA, costB);
            }
        }
        return dp[2 * n][n];
    }
}
```
### Algorithm
- Create a 2D DP table, `dp[i][j]`, to store the minimum cost for assigning the first `i` people with `j` of them going to city A.
- The table size will be `(2n + 1) x (n + 1)`.
- Initialize the table with a large value and set the base case `dp[0][0] = 0`.
- Iterate `i` from 1 to `2n` (representing the people).
- Iterate `j` from 0 to `n` (representing the count of people in city A).
- For each `dp[i][j]`, calculate the cost based on two possibilities for the `i`-th person:
  1. **Goes to City A:** `dp[i-1][j-1] + costs[i-1][0]`. This is valid if `j > 0`.
  2. **Goes to City B:** `dp[i-1][j] + costs[i-1][1]`. This is valid if the number of people in city B (`i-j`) does not exceed `n`.
- Set `dp[i][j]` to the minimum of the valid possibilities.
- The final answer is `dp[2n][n]`.

## Greedy Approach with Sorting
The most efficient approach is a greedy one. The core idea is to determine for each person the 'benefit' of sending them to city B instead of city A. This benefit can be calculated as `costB - costA`. To minimize the total cost, we should send the `n` people with the lowest `costB - costA` difference to city B, and the rest to city A.
**Time:** O(n log n), dominated by the sorting step of 2n elements. · **Space:** O(log n) or O(n), depending on the sorting algorithm's implementation details (e.g., space for recursion stack or auxiliary arrays). In Java, `Arrays.sort` for objects uses Timsort which can take O(n) space.
**Pros:** Most efficient solution with O(n log n) time complexity.; Relatively easy to understand and implement once the greedy insight is clear.
**Cons:** The greedy choice's correctness is not immediately obvious without a proof.
### Explanation
The problem can be reframed to make a greedy choice apparent. Suppose we tentatively send everyone to city A. The total cost would be the sum of all `aCost_i`. However, we must send `n` people to city B. When we change our decision for a person `i` from city A to city B, the total cost changes by `bCost_i - aCost_i`. Let's call this value the 'refund' for person `i`.

To minimize the final total cost, we should make this change for the `n` people who give us the best 'refund', i.e., those with the smallest `bCost_i - aCost_i` value. A negative refund is actually a saving, which is even better.

So, the strategy is to calculate this difference for every person, sort the people based on this difference, and send the `n` people with the smallest differences to city B. The other `n` people (with the largest differences) are sent to city A.

The total cost is then the sum of `bCost` for the first `n` people in the sorted list and `aCost` for the remaining `n` people.
```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        // Sort by the difference in costs, which represents the 'refund'
        // for sending a person to city B instead of city A.
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return (a[1] - a[0]) - (b[1] - b[0]);
            }
        });

        int minCost = 0;
        int n = costs.length / 2;

        // The first n people have the smallest bCost - aCost,
        // so they should go to city B to maximize the 'refund'.
        for (int i = 0; i < n; i++) {
            minCost += costs[i][1];
        }

        // The remaining n people have a larger bCost - aCost,
        // so it's cheaper to send them to city A.
        for (int i = n; i < 2 * n; i++) {
            minCost += costs[i][0];
        }

        return minCost;
    }
}
```
### Algorithm
- The key insight is to quantify the cost savings of sending a person to city B over city A. This is `costs[i][1] - costs[i][0]`.
- Sort the `costs` array in ascending order based on this difference.
- The first `n` people in the sorted list are those for whom sending to city B is most advantageous (or least disadvantageous). These people should be sent to city B.
- The remaining `n` people are sent to city A.
- Initialize a `totalCost` variable to 0.
- Iterate through the sorted `costs` array:
  - For the first `n` people (indices 0 to `n-1`), add their city B cost (`costs[i][1]`) to `totalCost`.
  - For the next `n` people (indices `n` to `2n-1`), add their city A cost (`costs[i][0]`) to `totalCost`.
- Return `totalCost`.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
class Solution { public: int twoCitySchedCost ( vector < vector < int >>& costs ) { sort ( costs . begin (), costs . end (), []( const vector < int >& a , const vector < int >& b ) { return a [ 0 ] - a [ 1 ] < b [ 0 ] - b [ 1 ]; }); int n = costs . size () / 2 ; int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { ans += costs [ i ][ 0 ] + costs [ i + n ][ 1 ]; } return ans ; } };
```

### Python

```python
class Solution : def twoCitySchedCost ( self , costs : List [ List [ int ]]) -> int : costs . sort ( key = lambda x : x [ 0 ] - x [ 1 ]) n = len ( costs ) >> 1 return sum ( costs [ i ][ 0 ] + costs [ i + n ][ 1 ] for i in range ( n ))
```