Вступить в клуб →
сложнаяpythonЖадные алгоритмы и интервалы

erase_overlap_count: минимум удалений, чтобы интервалы перестали пересекаться

Напишите функцию erase_overlap_count(intervals: list[list[int]]) -> int.

Вход. Список интервалов, каждый — список из двух целых [start, end], start <= end. Порядок произвольный, интервалы могут повторяться.

Выход. Минимальное количество интервалов, которые надо удалить, чтобы среди оставшихся не было пересекающихся (целое число).

Правила. Интервалы полуоткрытые: [1, 2] и [2, 3] не пересекаются и удалять ничего не нужно.

Поведение на краевых входах.

  • Пустой список — вернуть 0.
  • Один интервал — вернуть 0.
  • Три одинаковых интервала [1, 2] — вернуть 2: остаться должен ровно один.
  • Длинный интервал, перекрывающий несколько коротких, выгоднее удалить: для [[1, 100], [2, 3], [3, 4]] ответ 1.

Возвращать нужно именно количество удалённых интервалов, а не список оставшихся.

заготовка решения

def erase_overlap_count(intervals: list[list[int]]) -> int:
    # ваш код
    pass

🔒 Проверка ответа — для участников клуба

  • Автотесты прямо в браузере
  • Подсказка, если застряли
  • Разбор с объяснением, почему так
  • Прогресс по всем задачам и виртуальные собеседования
Зарегистрироваться →

Регистрация занимает минуту

Другие задачи раздела