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

158. Меньше всего смен модераторов на сутки

Средняя

Объявления проверяют круглосуточно. Модераторы предложили смены: смена [s, e) закрывает минуты от s включительно до e не включая.

Выберите наименьшее число смен, чтобы каждая минута отрезка [0, day) была закрыта хотя бы одной сменой. Смены могут пересекаться. Если покрыть нельзя — верните −1.

В работе: Составление графика модерации Авито на сутки: каждая лишняя смена — оплаченные часы, а дыра в графике — очередь непроверенных объявлений.

Пример 1

Ввод
shifts = [[0, 480], [300, 900], [480, 960], [900, 1440], [960, 1440]]
day = 1440
Вывод
3

Три смены, например `[0, 480)`, `[480, 960)`, `[960, 1440)`. Двумя не обойтись: ни одна смена не длиннее 600 минут.

Пример 2

Ввод
shifts = [[0, 600], [700, 1440]]
day = 1440
Вывод
-1

Минуты 600–699 никто не закрывает.

Ограничения

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

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