Couriers Grab Scooters

Medium

In the morning, couriers and e-scooters are scattered over a grid-shaped lot outside a warehouse. Courier i stands at couriers[i] = [x, y] and scooter j sits at scooters[j] = [x, y]. There are at least as many scooters as couriers. Scooters are handed out step by step. At each step, among all couriers still without a scooter and all scooters still free, take the pair with the smallest Manhattan distance |x1 - x2| + |y1 - y2|; that courier takes that scooter. If several pairs tie, the pair with the smaller courier index wins, and if the courier is the same, the smaller scooter index wins. Keep going until every courier has a scooter. Return an array answer where answer[i] is the (0-based) index of the scooter courier i ends up with.

Example 1

couriers=[[1, 1], [4, 0]], scooters=[[4, 2], [0, 0]] → [1, 0]

The closest pair is courier 0 with scooter 1 (distance 2). Courier 1 is also at distance 2 from scooter 0, but on a tie the courier with the smaller index goes first. Courier 1 then gets the only scooter left, 0.

Example 2

couriers=[[2, 2]], scooters=[[0, 2], [2, 0], [5, 5]] → [0]

Scooters 0 and 1 are both at distance 2; the one with the smaller index wins.

Example 3

couriers=[[0, 0], [0, 5], [6, 6]], scooters=[[0, 4], [0, 1], [9, 9], [6, 3]] → [1, 0, 3]

Constraints

1 ≤ len(couriers) ≤ len(scooters) ≤ 1000
Each point is a pair [x, y] with 0 ≤ x, y < 1000
No two couriers share a point, and no two scooters do (a courier may stand right at a scooter)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Sorting Heap (Priority Queue)