Least Total Walk to Scooters

Medium

Couriers and e-scooters are spread over a grid-shaped lot: 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. Every courier must get a scooter of their own (no scooter goes to two couriers). A courier walks to their scooter along the Manhattan distance |x1 - x2| + |y1 - y2|. Return the smallest possible total distance walked by all the couriers.

Example 1

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

Courier 0 takes scooter 1 (walk 2) and courier 1 takes scooter 0 (walk 2), 4 in total; scooter 2 stays unused.

Example 2

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

Either courier 0 takes scooter 0 and courier 1 takes scooter 1 (1 + 4 = 5), or the other way round (6 + 1 = 7). The answer is 5.

Example 3

couriers=[[3, 3]], scooters=[[3, 3]] → 0

The scooter is right where the courier stands, so no walking at all.

Constraints

1 ≤ len(couriers) ≤ len(scooters) ≤ 11
Each point is a pair [x, y] with 0 ≤ x, y < 1000
No two couriers share a point, and no two scooters do

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Dynamic Programming Backtracking Bitmask

Similar problems

Square Frame From Sticks Medium Seating by Divisibility Medium Cheapest Basket with Bundles Medium Groups With Equal Sums Medium Trainees and Coaches Medium

Input

couriers=[[0, 0], [5, 5]], scooters=[[4, 4], [1, 1], [9, 0]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 89 tests on the server, hidden ones included.