Слияние интервалов: сортировка, один проход и четыре задачи вокруг

Короткий ответ. Слияние интервалов делается в два шага. Сортируем отрезки по началу, потом идём по ним и склеиваем каждый с последним в ответе, если они пересекаются. Время O(n log n) из-за сортировки. Приём нужен в задачах про встречи, занятые слоты, вставку отрезка и покрытие. Ниже сигналы, код на Python, разбор и типичные ошибки.

Что такое слияние интервалов?

Интервал это пара чисел: начало и конец. Два интервала пересекаются, если начало второго не больше конца первого. Слияние заменяет пару пересекающихся отрезков одним, от меньшего начала до большего конца.

Без сортировки пришлось бы сравнивать каждый отрезок с каждым. Это O(n²). После сортировки по началу пересечься с текущим может только последний склеенный.

Отсюда весь приём: отсортировать, потом один проход.

Слово «интервал» в задачах значит разное: время встречи, отрезок на прямой, диапазон индексов. Приём одинаков для всех трёх. Важно только, что есть начало и конец, и их можно сравнивать.

По каким словам в задаче узнать слияние интервалов?

• «Объединить пересекающиеся отрезки».
• «Вставить новый интервал в список без пересечений».
• «Сколько переговорок нужно для встреч».
• «Может ли один человек посетить все встречи».

Общий признак: дан список пар начало-конец, и вопрос про пересечения или покрытие. Если вопрос «сколько отрезков одновременно», это соседний приём, линия развёртки.

Как работает слияние интервалов по шагам?

• Сортируем отрезки по началу.
• Кладём первый в ответ.
• Для каждого следующего смотрим на последний в ответе. Начало текущего не больше его конца, значит пересекаются. Обновляем конец последнего максимумом двух концов.
• Иначе кладём текущий в ответ как новый отрезок.

Максимум концов нужен потому, что текущий отрезок может целиком лежать внутри предыдущего.

Как это выглядит на примере?

Отрезки [1, 3], [8, 10], [2, 6], [15, 18]. После сортировки: [1, 3], [2, 6], [8, 10], [15, 18].

Ответ: [1, 3]. Берём [2, 6]: 2 не больше 3, склеиваем, ответ [1, 6]. Берём [8, 10]: 8 больше 6, новый отрезок. Берём [15, 18]: 15 больше 10, новый. Итог [1, 6], [8, 10], [15, 18].

Как написать слияние интервалов на Python?

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    result = []
    for start, end in intervals:
        if result and start <= result[-1][1]:
            result[-1][1] = max(result[-1][1], end)   # пересекаются
        else:
            result.append([start, end])
    return result

def insert(intervals, new):
    result, i, n = [], 0, len(intervals)
    while i < n and intervals[i][1] < new[0]:      # целиком левее
        result.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= new[1]:     # пересекаются с новым
        new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])]
        i += 1
    result.append(new)
    result.extend(intervals[i:])                    # целиком правее
    return result

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

Чем слияние отличается от соседних задач на интервалы?

Задача	Сортировка по	Что делаем в проходе	Время
Merge Intervals	Началу	Склеиваем с последним	O(n log n)
Insert Interval	Уже отсортировано	Три цикла: до, внутри, после	O(n)
Meeting Rooms	Началу	Ищем начало раньше прошлого конца	O(n log n)
Meeting Rooms II	Началу плюс куча концов	Считаем максимум одновременных	O(n log n)
Non-overlapping Intervals	Концу	Жадно оставляем самый ранний конец	O(n log n)

Как решить Meeting Rooms II?

Дан список встреч. Нужно минимальное число переговорок. Сортируем по началу. Держим кучу концов идущих встреч.

Для каждой встречи: если самый ранний конец в куче не больше её начала, та встреча закончилась, снимаем конец. Кладём конец текущей. Размер кучи в пике и есть ответ.

Как решить Non-overlapping Intervals?

Нужно удалить минимум отрезков, чтобы остальные не пересекались. Сортируем по концу. Держим конец последнего оставленного.

Отрезок начинается раньше этого конца, удаляем его. Иначе оставляем и обновляем конец. Обычно сортируют по концу. По началу тоже можно, если при пересечении оставлять отрезок, который кончается раньше.

Как решить Meeting Rooms?

Может ли один человек посетить все встречи? Сортируем по началу. Идём по парам соседей. Если начало следующей встречи меньше конца предыдущей, две встречи пересекаются, ответ нет. Дошли до конца без пересечений, ответ да. Это слияние без самого слияния.

На каких ошибках ломается слияние интервалов?

• Забывают сортировку и склеивают только соседей по входу.
• Берут конец текущего вместо максимума концов. Вложенный отрезок укорачивает ответ.
• Путают строгое и нестрогое сравнение на касании. [1, 3] и [3, 5] по условию могут быть и одним, и двумя.
• Меняют кортежи вместо списков и получают ошибку присваивания.

Как объяснить приём на собеседовании?

Скажите: сортирую по началу, тогда пересечься с текущим может только последний склеенный. Назовите O(n log n) и объясните, что это сортировка, а проход линейный.

Уточните у собеседующего, считается ли касание пересечением. Это показывает внимание к краям.

Отработать узнавание приёма можно на странице интервалы: слияние и вставка. Соседний приём разобран на странице линия развёртки.

Вопросы и ответы

Можно ли обойтись без сортировки?

Только если вход уже отсортирован или координаты маленькие целые. Во втором случае подходит массив разностей за O(n + max).

Как найти пересечение двух списков интервалов?

Два указателя, по одному на список. Пересечение это максимум начал и минимум концов, если первое не больше второго. Двигаем тот указатель, чей отрезок кончается раньше.

Что делать с открытыми и закрытыми концами?

Решить один раз в начале и держать одно сравнение. Для закрытых концов пересечение при start не больше end. Для открытых при строгом меньше.

Где приём встречается в реальных системах?

В календарях при поиске свободного слота. В планировщиках, которые сливают занятые окна. В работе с диском, где склеивают соседние свободные блоки.