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

140. Меньше всего смен на круглосуточную линию

Средняя

Линия поддержки Альфа‑Банка работает круглосуточно: сутки — это минуты [0, day). Операторы заявили смены shifts[i] = [start, end) — с минуты start до минуты end, не включая её.

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

В работе: Планирование на праздники: из 40 заявленных смен оставить 6–7 и не оголить линию ночью.

Пример 1

Ввод
day = 1440
shifts = [[0, 480], [420, 900], [480, 1000], [960, 1440], [600, 1200]]
Вывод
3

[0, 480), [480, 1000), [960, 1440) — три смены.

Пример 2

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

С 600 до 700 никого — −1.

Ограничения

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

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