11057. Campus Bikes

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.

Note: Each element in people or scooters is a string where x and y coordinates are separated by space.

Examples

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

Constraints

  • 0 <= people[i], scooters[j] < 2000 for both coordinates.
  • All coordinates for people and scooters are distinct.
  • 1 <= people.length <= scooters.length <= 800




Please use Laptop/Desktop or any other large screen to add/edit code.