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

141. Снять меньше всего пересекающихся поднятий

Средняя

В рубрике Авито есть один верхний слот выдачи. Продавцы купили поднятия: заявка [start, end) занимает слот с минуты start до минуты end, не включая её.

Две заявки конфликтуют, если их отрезки пересекаются; касание концами ([10, 20) и [20, 30)) — не конфликт. Посчитайте, сколько заявок придётся снять, чтобы оставшиеся не конфликтовали, если снимать как можно меньше.

В работе: Снятые заявки возвращают деньги или переносят: чем меньше снятых, тем меньше возвратов.

Пример 1

Ввод
slots = [[0, 30], [10, 20], [20, 40], [35, 50]]
Вывод
2

Без конфликтов больше двух не оставить, например [10, 20) и [20, 40): снять две заявки.

Пример 2

Ввод
slots = [[0, 60], [60, 120]]
Вывод
0

Касание концами — снимать нечего.

Ограничения

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

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