On a city map represented as a 2D grid, there are P
people and Q
scooters, with P <= Q
. Each person and scooter has a unique pair of 2D coordinates on the grid.
Your task is to assign a scooter to each person. At each step, you should select the (person, scooter) pair with the smallest Manhattan distance between them. If there are multiple pairs with the same minimal distance, choose the one with the lowest person index. If there are still ties, select the pair with the lowest scooter index. Continue this process until every person has a scooter.
The Manhattan distance between two points a
and b
is defined as |a.x - b.x| + |a.y - b.y|
.
Return an array result
of length P
, where result[i]
is the index (0-based) of the scooter assigned to the i
-th person.
Example 1:
Input: people = ["0 0","3 2"], scooters = ["2 3","1 1"] Output: [1,0] Explanation: Person 1 is closest to Scooter 0, so they are paired first. Person 0 is assigned Scooter 1. Thus, the output is [1,0].
Example 2:
Input: people = ["1 0","2 2","3 1"], scooters = ["2 1","3 3","1 2"] Output: [0,2,1] Explanation: Person 0 pairs with Scooter 0 first. Person 1 and Person 2 are both equally close to Scooter 2, so Person 1 pairs with Scooter 2 (lower index). Person 2 gets Scooter 1. So the output is [0,2,1].
0 <= people[i], scooters[j] < 2000
for both coordinates.1 <= people.length <= scooters.length <= 800