# LeetCode 1057: Campus Bikes

## Problem Restatement

We have a campus as a 2D grid. We are given the positions of `n` workers and `m` bikes.

We need to assign one bike to each worker.

We assign bikes greedily:
1. Find the pair `(worker, bike)` with the smallest Manhattan distance.
2. Assign that bike to that worker.
3. Remove both from consideration.
4. Repeat.

If there are ties in distance, pick the smallest worker index, then smallest bike index.

Return an array where `result[i]` is the bike index assigned to worker `i`.

The official constraints state that `0 <= workers.length <= 1000` and `0 <= bikes.length <= 1000`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Worker positions and bike positions |
| Output | Bike assignment for each worker |

Function shape:

```python
def assignBikes(workers: list[list[int]], bikes: list[list[int]]) -> list[int]:
    ...
```

## Examples

Example 1:

```python
workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
```

Distances: `(0,0)→(1,2)`: 3, `(0,0)→(3,3)`: 6, `(2,1)→(1,2)`: 2, `(2,1)→(3,3)`: 3.

Minimum is 2: worker 1 gets bike 0. Then worker 0 gets bike 1.

Answer:

```python
[1, 0]
```

## Key Insight

Compute all `(distance, worker_idx, bike_idx)` triples, sort them, then greedily assign.

## 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 * m * log(n * m))` | Sort all pairs |
| Space | `O(n * m)` | All pairs stored |

## 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 assignBikes(self, workers: list[list[int]], bikes: list[list[int]]) -> list[int]:
        pairs = []
        for i, (wr, wc) in enumerate(workers):
            for j, (br, bc) in enumerate(bikes):
                dist = abs(wr - br) + abs(wc - bc)
                pairs.append((dist, i, j))

        pairs.sort()
        assigned_worker = set()
        assigned_bike = set()
        result = [-1] * len(workers)

        for dist, w, b in pairs:
            if w not in assigned_worker and b not in assigned_bike:
                result[w] = b
                assigned_worker.add(w)
                assigned_bike.add(b)
                if len(assigned_worker) == len(workers):
                    break

        return result
```

## Testing

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

    assert s.assignBikes([[0,0],[2,1]], [[1,2],[3,3]]) == [1, 0]
    assert s.assignBikes([[0,0],[1,1],[2,0]], [[1,0],[2,2],[2,1]]) == [0, 2, 1]

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---|---|
| 2 workers, 2 bikes | `[1,0]` | Closest pair assigned first |
| 3 workers, 3 bikes | `[0,2,1]` | Greedy distance order |