# LeetCode 1029: Two City Scheduling

## Problem Restatement

We have `2n` people who must each travel to one of two cities: city A or city B.

Exactly `n` people must go to city A and exactly `n` must go to city B.

The cost to send person `i` to city A is `costs[i][0]` and to city B is `costs[i][1]`.

We need to return the minimum total cost.

The official constraints state that `2 <= costs.length <= 200`, `costs.length` is even, and `1 <= costs[i][0], costs[i][1] <= 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `costs` where `costs[i] = [aCost, bCost]` |
| Output | Minimum total cost to send `n` people to each city |

Function shape:

```python
def twoCitySchedCost(costs: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

```python
costs = [[10,20],[30,200],[400,50],[30,20]]
```

Send persons 0, 1 to A: `10 + 30 = 40`. Send persons 2, 3 to B: `50 + 20 = 70`. Total: `110`.

Answer:

```python
110
```

## Key Insight

Start by sending everyone to city A. Cost = `sum(costs[i][0])`.

Now we need to switch `n` people to city B. Switching person `i` from A to B costs an extra:

```python
costs[i][1] - costs[i][0]
```

This is the "refund" (can be negative, meaning cheaper).

To minimize total cost, sort by this difference and switch the `n` people with the smallest differences.

## Algorithm

1. Compute base cost: send everyone to A.
2. Compute `diff[i] = costs[i][1] - costs[i][0]` for each person.
3. Sort `diff`.
4. Add the `n` smallest differences to the base cost.
5. Return total.

## Correctness

Sending everyone to A gives the base cost. Switching person `i` to B changes the cost by `costs[i][1] - costs[i][0]`.

We must switch exactly `n` people. To minimize the total change, pick the `n` people with the smallest switching cost (most negative differences benefit us most).

## Edge Cases

- Check the minimum input size allowed by the constraints.
- Verify duplicate values or tie cases if the input can contain them.
- Keep the return value aligned with the exact failure case in the statement.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting |
| Space | `O(1)` | Sort in place |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

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

## Code Explanation

Sort by the cost difference (benefit of going to B vs A):

```python
costs.sort(key=lambda c: c[1] - c[0])
```

Those with the smallest (most negative) difference benefit most from going to B.

Send the first `n` (cheapest to redirect to B) to B, and the last `n` to A:

```python
sum(costs[i][0] for i in range(n)) + sum(costs[i][1] for i in range(n, 2 * n))
```

Wait — those sorted first (smallest `b - a`) are cheapest to send to B. So send them to B and the rest to A.

After sorting by `costB - costA`, the first `n` people are cheapest to send to city B relative to city A, and the remaining `n` people go to city A. Therefore:

- First `n`: send to **B** → `costs[i][1]`
- Last `n`: send to **A** → `costs[i][0]`

## Testing

```python
def run_tests():
    s = Solution()

    assert s.twoCitySchedCost([[10,20],[30,200],[400,50],[30,20]]) == 110
    assert s.twoCitySchedCost([[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]) == 1859

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| 4-person example | `110` | Optimal assignment splits costs |
| 6-person example | `1859` | Greedy refund approach |