Non-overlapping Intervals

Средняя№435сортировка по концу

Дан список интервалов. Нужно убрать как можно меньше из них, чтобы никакие два оставшихся не пересекались, и вернуть, сколько убрано. Интервалы, которые только касаются, как [1, 3] и [3, 5], не пересекаются. Наш пример: [4, 7], [0, 9], [8, 11], [1, 3], [10, 12], [3, 5], [6, 8] — ответ 3.

435 Non-overlapping IntervalsРазбор · 1×

Пример: [4, 7], [0, 9], [8, 11], [1, 3], [10, 12], [3, 5], [6, 8]. Интервалы нарисованы по порядку концов; оставленные собраны в нижней строке.

[1, 3][3, 5][4, 7][6, 8][0, 9][8, 11][10, 12]итог0123456789101112
ещё впередитекущий интервалоставленубран

Сортируем по концу: 3, 5, 7, 8, 9, 11, 12

01/25
сначала · назад · пуск · шаг
Скорость
1function eraseOverlapIntervals(intervals):
2 sort intervals by end
3 removed = 0
4 lastEnd = -infinity
5 for each [start, end] in intervals:
6 if start >= lastEnd:
7 lastEnd = end
8 else:
9 removed = removed + 1
10 return removed
состояние
removed
–
lastEnd
–
start
–
end
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Убрать как можно меньше — то же, что оставить как можно больше. Интервал, который кончается раньше всех, всегда стоит оставить: любой другой выбор кончается позже и оставляет остальным меньше места.
  2. Дальше тот же выбор повторяется среди тех, что начинаются не раньше его конца. По порядку концов это один проход: интервал остаётся, если начало ≥ lastEnd, иначе он пересекает последний оставленный — убираем.
  3. Сортировка по началу здесь ошиблась бы: [0, 9] начинается раньше всех, и, оставив его, мы закрыли бы [1, 3], [3, 5] и [6, 8].

Сложность

Время O(n log n): сортировка; проход после неё — O(n). Память O(1), не считая того, что нужно сортировке.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.