Merge Intervals

Средняя№56слияние

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

56 Merge IntervalsРазбор · 1×

Пример: [9, 12], [1, 4], [5, 7], [4, 5], [10, 11]. Каждый интервал — полоска на оси, по порядку начал; внизу строка результата.

[1, 4][4, 5][5, 7][9, 12][10, 11]итог0123456789101112
ещё впередитекущий интервалпоследний в результатерезультатуже учтён

Сортируем по началу: [1, 4], [4, 5], [5, 7], [9, 12], [10, 11]

01/18
сначала · назад · пуск · шаг
Скорость
1function merge(intervals):
2 sort intervals by start
3 result = []
4 for each [start, end] in intervals:
5 if result is empty or start > result.last.end:
6 add [start, end] to result
7 else:
8 result.last.end = max(result.last.end, end)
9 return result
состояние
result
–
start
–
end
–
историянажмите шаг, чтобы вернуться

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

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

  1. После сортировки по началу за интервалом, который начинается правее конца последней группы, идут только интервалы, начинающиеся ещё правее. Ни один из них не дотянется назад до группы, поэтому группа идёт подряд.
  2. Поэтому каждый интервал сравниваем только с последним в результате: если он начинается не позже его конца — сливаем, иначе он открывает новую группу.
  3. Конец становится максимумом двух концов, а не просто новым концом: [10, 11] лежит внутри [9, 12], и его конец обрезал бы интервал.

Сложность

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

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

Решить на LeetCode ↗

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