Войти Регистрация
Алгоритмы

88. Раздать заявки аналитикам

Сложная

В отдел платёжных сервисов Сбера пришло n заявок на разбор спорных списаний, в смене n аналитиков. minutes[i][j] — сколько минут аналитик i потратит на заявку j: у кого-то опыт с картами, у кого-то с переводами по СБП.

Каждому аналитику — ровно одна заявка, каждая заявка — ровно одному аналитику. Верните минимальное суммарное время.

В работе: Назначение исполнителей при малом n: смены, слоты, станки. Для больших n — венгерский алгоритм.

Пример 1

Ввод
minutes = [[9, 2, 7], [6, 4, 3], [5, 8, 1]]
Вывод
9

0 → 1, 1 → 0, 2 → 2: 2 + 6 + 1 = 9.

Пример 2

Ввод
minutes = [[5]]
Вывод
5

Ограничения

  • 1 ≤ n ≤ 16
  • 1 ≤ minutes[i][j] ≤ 1000
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def assign_requests(minutes):
ДП по подмножествамБитовые маскиЗадача о назначенияхцельпо числу ответов

Источник: наша задача на данных Сбера. Условие пересказано своими словами.