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

157. Меньше всего рейсов за партиями на рампе

Средняя

На рампе сортировочного центра партия i лежит с минуты windows[i][0] по минуту windows[i][1] включительно, потом её уносят обратно на склад.

Машина подъезжает в любую целую минуту t и мгновенно забирает все партии, у которых l ≤ t ≤ r. Сколько рейсов нужно, чтобы забрать все партии?

В работе: Планирование подъездов магистральной машины к рампе сортировочного центра Ozon: каждый лишний рейс — около 40 минут работы водителя.

Пример 1

Ввод
windows = [[10, 30], [20, 50], [40, 60], [55, 70]]
Вывод
2

Рейсы в минуты 30 (две первые партии) и 60 (две последние).

Пример 2

Ввод
windows = [[5, 5], [5, 5]]
Вывод
1

Одна минута, один рейс.

Ограничения

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

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