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

MediumАлгоритмы
05:00
Лучше работает на десктопе
GreedySortingIntervals

Дан массив интервалов 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
Консоль
Нажмите Run или Ctrl+Enter для запуска