## Description

https://leetcode.com/problems/campus-bikes/

On a campus represented on the X-Y plane, there are `n`

workers and `m`

bikes, with `n <= m`

.

You are given an array `workers`

of length `n`

where `workers[i] = [x`

is the position of the _{i}, y_{i}]`i`

worker. You are also given an array ^{th}`bikes`

of length `m`

where `bikes[j] = [x`

is the position of the _{j}, y_{j}]`j`

bike. All the given positions are ^{th}**unique**.

Assign a bike to each worker. Among the available bikes and workers, we choose the `(worker`

pair with the shortest _{i}, bike_{j})**Manhattan distance** between each other and assign the bike to that worker.

If there are multiple `(worker`

pairs with the same shortest _{i}, bike_{j})**Manhattan distance**, we choose the pair with **the smallest worker index**. If there are multiple ways to do that, we choose the pair with **the smallest bike index**. Repeat this process until there are no available workers.

Return *an array *`answer`

* of length *`n`

*, where *`answer[i]`

* is the index ( 0-indexed) of the bike that the *

`i`^{th}

*worker is assigned to*.

The **Manhattan distance** between two points `p1`

and `p2`

is `Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|`

.

**Example 1:**

Input:workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]Output:[1,0]Explanation:Worker 1 grabs Bike 0 as they are closest (without ties), and Worker 0 is assigned Bike 1. So the output is [1, 0].

**Example 2:**

Input:workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]Output:[0,2,1]Explanation:Worker 0 grabs Bike 0 at first. Worker 1 and Worker 2 share the same distance to Bike 2, thus Worker 1 is assigned to Bike 2, and Worker 2 will take Bike 1. So the output is [0,2,1].

**Constraints:**

`n == workers.length`

`m == bikes.length`

`1 <= n <= m <= 1000`

`workers[i].length == bikes[j].length == 2`

`0 <= x`

_{i}, y_{i}< 1000`0 <= x`

_{j}, y_{j}< 1000- All worker and bike locations are
**unique**.

## Python Solution

Build a distance map so that we can assign bike worker pairs in ascending order. Use hashsets to track assigned bikes and workers.

```
class Solution:
def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:
results = [None for i in range(len(workers))]
distances = defaultdict(list)
for worker_index, worker in enumerate(workers):
for bike_index, bike in enumerate(bikes):
distance = self.get_distance(worker, bike)
distances[distance].append([worker_index, bike_index])
assigned_workers = set()
assigned_bikes = set()
for key in sorted(distances.keys()):
for pair in distances[key]:
if pair[0] not in assigned_workers and pair[1] not in assigned_bikes:
results[pair[0]] = pair[1]
assigned_workers.add(pair[0])
assigned_bikes.add(pair[1])
return results
def get_distance(self, worker, bike):
return abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])
```

- Time Complexity: O(MN).
- Space Complexity: O(N).