Insert Interval

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

Дан список интервалов, отсортированный по началу, без пересечений, и один новый интервал. Нужно вставить новый, слить его со всеми интервалами, с которыми он пересекается или соприкасается, и вернуть список — по-прежнему отсортированный и без пересечений. Наш пример: [0, 2], [3, 5], [7, 8], [9, 12] и новый [4, 7] — ответ [0, 2], [3, 8], [9, 12].

57 Insert IntervalРазбор · 1×

Пример: [0, 2], [3, 5], [7, 8], [9, 12], новый [4, 7]. Сверху список, под ним новый интервал [lo, hi], ниже результат.

[0, 2][3, 5][7, 8][9, 12]итог0123456789101112
ещё впередиintervals[i]новый интервал [lo, hi]уже учтёнрезультат

Результат пока пуст

01/20
сначала · назад · пуск · шаг
Скорость
1function insert(intervals, newInterval):
2 result = []
3 [lo, hi] = newInterval
4 i = 0; n = len(intervals)
5 while i < n and intervals[i].end < lo:
6 add intervals[i] to result; i = i + 1
7 while i < n and intervals[i].start <= hi:
8 lo = min(lo, intervals[i].start)
9 hi = max(hi, intervals[i].end)
10 i = i + 1
11 add [lo, hi] to result
12 while i < n:
13 add intervals[i] to result; i = i + 1
14 return result
состояние
result
[]
lo
–
hi
–
i
–
историянажмите шаг, чтобы вернуться

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

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

  1. Список отсортирован и без пересечений, поэтому делится на три куска подряд: интервалы, которые кончаются до lo, интервалы, пересекающие новый, и интервалы правее него. Сортировать не нужно.
  2. Каждый пересекающийся интервал расширяет [lo, hi]: минимум начал и максимум концов. Вместо всех них в результат идёт один слитый интервал, поэтому пересечений в нём нет.
  3. Касание считается пересечением, и знаки это учитывают: конец < lo оставляет интервал в стороне, только если он кончается раньше lo, а начало ≤ hi впускает [7, 8], хотя он только начинается в hi = 7.

Сложность

Время O(n): за три цикла каждый интервал просматривается один раз. Память O(n) на результат.

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

Решить на LeetCode ↗

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