> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Two City Scheduling Python Solution with Tests

> Tested Python solution for LeetCode 1029 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 1029, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Greedy](/catalog/topics/greedy), [Sorting](/catalog/topics/sorting). [View on LeetCode](https://leetcode.com/problems/two-city-scheduling/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1029   # by problem number
lcpy gen -s two_city_scheduling   # by problem name
```

## 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.

### Examples

```
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.
```

```
Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859
Explanation: For example, the way to achieve the minimum of 1859 is:
- Fly the 1st person (259, 770) to city A for 259.
- Fly the 2nd person (448, 54) to city B for 54.
- Fly the 3rd person (926, 667) to city B for 667.
- Fly the 4th person (184, 139) to city B for 139.
- Fly the 5th person (840, 118) to city B for 118.
- Fly the 6th person (577, 469) to city A for 577.
The total minimum cost is 1859.
```

```
Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
Output: 3086
Explanation: The total minimum cost is 3086.
```

### Constraints

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/two_city_scheduling/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/two_city_scheduling/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n log n)
    # Space: O(n) for the sorted copy
    def two_city_sched_cost(self, costs: list[list[int]]) -> int:
        ordered = sorted(costs, key=lambda cost: cost[0] - cost[1])
        n = len(ordered) // 2
        return sum(cost[0] for cost in ordered[:n]) + sum(cost[1] for cost in ordered[n:])
```

## Complexity

| Time | Space |
| - | - |
| O(n log n) | O(n) for the sorted copy |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.