Сложность: medium
В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Пример:
Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]
👨💻 Алгоритм:
1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.
2⃣Отсортируй список пар по расстоянию, а затем по индексу работника и велосипеда.
Назначь велосипеды работникам, следуя отсортированному списку пар и отслеживая, какие работники и велосипеды уже были использованы.
3⃣Заполни и верни массив назначений.
😎 Решение:
def assignBikes(workers, bikes):
pairs = []
for i, (wx, wy) in enumerate(workers):
for j, (bx, by) in enumerate(bikes):
distance = abs(wx - bx) + abs(wy - by)
pairs.append((distance, i, j))
pairs.sort()
result = [-1] * len(workers)
bike_taken = [False] * len(bikes)
worker_assigned = [False] * len(workers)
for distance, worker_idx, bike_idx in pairs:
if not worker_assigned[worker_idx] and not bike_taken[bike_idx]:
result[worker_idx] = bike_idx
bike_taken[bike_idx] = True
worker_assigned[worker_idx] = True
return result
Ставь 👍 и забирай 📚 Базу знаний