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

120. Провести платежи до срока с наибольшей комиссией

Сложная

Шлюз Сбера проводит один платёж за слот, слоты нумеруются с 1. Дан список payments из пар [deadline, fee]: платёж нужно провести в слоте с номером не больше deadline, тогда банк получит комиссию fee.

Платежи, которые не успеваем, отклоняем. Верните наибольшую сумму комиссий за успевшие платежи.

В работе: Вечером в очереди 40 000 платёжных поручений юрлиц, а до закрытия операционного дня — 12 000 слотов: какие провести.

Пример 1

Ввод
payments = [[1, 50], [1, 70], [2, 30], [2, 60]]
Вывод
130

Слот 1 — платёж за 70, слот 2 — за 60: 130.

Пример 2

Ввод
payments = [[3, 10]]
Вывод
10

Один платёж успевает.

Ограничения

  • 0 ≤ длина payments ≤ 10⁵
  • 1 ≤ deadline ≤ 10⁵
  • 1 ≤ fee ≤ 10⁶
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def max_on_time_fee(payments):
Жадный алгоритмКучаСортировкацельO(n log n)

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