Interval List Intersections

Средняя№986два списка

Даны два списка интервалов. Каждый отсортирован, и внутри одного списка интервалы не пересекаются. Нужно вернуть по порядку все общие куски интервала из первого списка и интервала из второго. Общий кусок может быть и одной точкой. Наш пример: A = [1, 3], [5, 9], [11, 12], B = [0, 2], [4, 6], [8, 12] — ответ [1, 2], [5, 6], [8, 9], [11, 12].

986 Interval List IntersectionsРазбор · 1×

Пример: A = [1, 3], [5, 9], [11, 12], B = [0, 2], [4, 6], [8, 12]. Каждый список — строка на оси; линии показывают lo и hi, внизу результат.

ABитог0123456789101112
ещё впередиA[i] и B[j], новый общий кусокуже учтёнрезультат

Общих кусков пока нет

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

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

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

  1. У двух интервалов общий кусок от более позднего начала, lo, до более раннего конца, hi. Если lo > hi, один кончается раньше, чем начинается другой, и общего нет.
  2. Интервал, который кончается раньше, отработал: все следующие интервалы другого списка начинаются после конца текущего, а он и так дальше этого конца. Поэтому сдвигается он, а второй остаётся.
  3. Оставшийся может встретить ещё что-то: [8, 12] из B даёт [8, 9] с [5, 9], а потом [11, 12] с [11, 12]. Если сдвигать оба сразу, второй кусок потеряется.

Сложность

Время O(n + m): каждый шаг продвигает один из двух списков. Память O(1), не считая результата.

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

Решить на LeetCode ↗

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