Ctrl K

Брони, которые никто не поглотил

Средняя
В переговорной записаны брони slots: каждая бронь [start, end) занимает время от start включительно до end не включительно. Бронь [a, b) считается лишней, если в списке есть другая бронь [c, d), которая её полностью покрывает: c ≤ a и b ≤ d. Все лишние брони вычёркивают. Верните, сколько броней останется.
Пример 1
slots=[[2, 6], [3, 5], [7, 9], [4, 8]] → 3

Бронь [3, 5) целиком лежит внутри [2, 6) и вычёркивается. Остальные три ни в какой другой не помещаются: ответ 3.

Пример 2
slots=[[0, 10], [0, 4], [6, 10]] → 1

Обе короткие брони входят в [0, 10), даже если делят с ней границу. Остаётся одна.

Пример 3
slots=[[1, 3], [3, 5]] → 2
Ограничения
  • 1 ≤ len(slots) ≤ 1000
  • slots[i] = [start, end], 0 ≤ start < end ≤ 10⁵
  • Все брони различны
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиТройки с нулевой суммой СредняяСумма тройки ближе всего к цели СредняяЧетыре числа с заданной суммой СредняяРазличные перестановки с повторами СредняяРазложить анаграммы по группам Средняя
загружаем Python…
Вход
slots=[[2, 6], [3, 5], [7, 9], [4, 8]]
Ожидается
3

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 107 тестов на сервере, включая скрытые.