Ctrl K

Курьеры разбирают самокаты

Средняя
Утром у склада на клетчатой площадке стоят курьеры и электросамокаты. Курьер i стоит в точке couriers[i] = [x, y], самокат j — в точке scooters[j] = [x, y]. Самокатов не меньше, чем курьеров. Самокаты раздаются по шагам. На каждом шаге среди всех ещё свободных курьеров и свободных самокатов выбирается пара с наименьшим манхэттенским расстоянием |x1 - x2| + |y1 - y2|, и курьер забирает этот самокат. Если таких пар несколько, побеждает пара с меньшим номером курьера, а при равных курьерах — с меньшим номером самоката. Раздача идёт, пока у каждого курьера не будет самоката. Верните массив answer, где answer[i] — номер самоката (с нуля), который достался курьеру i.
Пример 1
couriers=[[1, 1], [4, 0]], scooters=[[4, 2], [0, 0]] → [1, 0]

Самая короткая пара — курьер 0 и самокат 1 (расстояние 2); курьер 1 и самокат 0 тоже на расстоянии 2, но при равенстве первым выбирает курьер с меньшим номером. Затем курьеру 1 достаётся единственный оставшийся самокат 0.

Пример 2
couriers=[[2, 2]], scooters=[[0, 2], [2, 0], [5, 5]] → [0]

Самокаты 0 и 1 на одинаковом расстоянии 2; берётся тот, у кого номер меньше.

Пример 3
couriers=[[0, 0], [0, 5], [6, 6]], scooters=[[0, 4], [0, 1], [9, 9], [6, 3]] → [1, 0, 3]
Ограничения
  • 1 ≤ len(couriers) ≤ len(scooters) ≤ 1000
  • Каждая точка — пара [x, y], 0 ≤ x, y < 1000
  • Все курьеры стоят в разных точках, все самокаты — тоже (курьер может стоять прямо у самоката)
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиK-й результат сверху СредняяСтудии для записи СредняяСамые частые значения СредняяK-е по величине в упорядоченной таблице СредняяЗадания с перерывом на остывание Средняя
загружаем Python…
Вход
couriers=[[1, 1], [4, 0]], scooters=[[4, 2], [0, 0]]
Ожидается
[1, 0]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 95 тестов на сервере, включая скрытые.