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

198. Рейсы одной фуры с наибольшей выручкой

Сложная

Перевозчику, работающему с Ozon, предложили рейсы [start, end, money]: часы начала и окончания и выплату в рублях. У перевозчика одна фура, рейсы не могут идти одновременно; следующий можно начать в тот же час, когда закончился предыдущий.

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

В работе: На неделю в кабинете перевозчика 400 рейсов: жадный выбор «самый дорогой первым» ошибается уже на трёх рейсах, а перебор наборов — 2⁴⁰⁰.

Пример 1

Ввод
trips = [[0, 6, 30000], [5, 9, 14000], [6, 12, 25000], [10, 14, 12000]]
Вывод
55000

Рейсы 0–6 и 6–12: 55 000 ₽.

Пример 2

Ввод
trips = [[0, 10, 50000], [0, 5, 20000], [5, 10, 20000]]
Вывод
50000

Один длинный рейс выгоднее двух коротких.

Ограничения

  • 1 ≤ n ≤ 10⁵
  • 0 ≤ start < end ≤ 10⁹
  • 1 ≤ money ≤ 10⁶
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def best_truck_plan(trips):
Динамическое программированиеИнтервалыБинарный поискцельO(n log n)

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