К задачам

Максимальное количество непересекающихся интервалов

СредняяАлгоритмы
Лучше работает на десктопе
Жадный алгоритмСортировкаIntervals

Дан массив интервалов intervals, где intervals[i] = [start_i, end_i]. Верните минимальное количество интервалов, которое нужно удалить, чтобы остальные не пересекались.

Интервалы [1, 2] и [2, 3] НЕ считаются пересекающимися.

Сигнатура

def erase_overlap_intervals(intervals: list[list[int]]) -> int:

Constraints

  • 1 ≤ len(intervals) ≤ 10⁵
  • intervals[i].length == 2
  • -5 × 10⁴ ≤ start_i < end_i ≤ 5 × 10⁴

Примеры

Пример 1

Вход:
intervals = [[1,2],[2,3],[3,4],[1,3]]
Выход:1

Пример 2

Вход:
intervals = [[1,2],[1,2],[1,2]]
Выход:2

Пример 3

Вход:
intervals = [[1,2],[2,3]]
Выход:0
Код
Python · Ctrl/⌘ + Enter для запуска
Лимит
05:00
Консоль
Нажмите кнопку запуска или Ctrl+Enter
Максимальное количество непересекающихся интервалов — Алгоритмы задача — ML Mentor