---
title: "Интервалы: слияние и вставка"
url: https://algopath.pro/ru/patterns/intervals-merge
language: ru
summary: "Отсортируйте интервалы по началу и пройдите их один раз. Соседи сливаются, если следующее начало не позже текущего конца."
updated: 2026-08-24
---

# Интервалы: слияние и вставка

Отсортируйте интервалы по началу и пройдите их один раз. Соседи сливаются, если следующее начало не позже текущего конца.

## Интервалы: слияние и вставка: как это работает?

Отсортируйте интервалы по значению начала. Без этого порядка дальше ничего не работает.

Возьмите первый интервал как текущий блок. Все следующие сравниваются с ним.

Посмотрите на следующий интервал и его начало. Сравните это начало с текущим концом.

Если начало не позже текущего конца, интервалы соприкасаются. Расширьте конец до большего из двух.

Если начало позже, блок закончен. Запишите его и сделайте новый интервал текущим.

Один проход покрывает весь список. Последний блок записывается после цикла.

- `текущий = [1, 3]` Список отсортирован по началу. Первый интервал открывает блок.
- `следующий = [2, 6]` 2 не позже 3, значит есть пересечение. Конец растёт до 6.
- `текущий = [1, 6], следующий = [8, 10]` 8 позже 6. Блок закончен и записан.
- `текущий = [8, 10], следующий = [9, 12]` 9 не позже 10. Конец растёт до 12.
- `[[1, 6], [8, 12]]` Последний блок записан после цикла. Четыре интервала стали двумя.

## Интервалы: слияние и вставка: когда применять?

- слить перекрывающиеся интервалы
- вставить новый интервал в отсортированный список
- встречи, брони или диапазоны, которые пересекаются
- заданы как пары [начало, конец]
- свободное/занятое время между интервалами

## Интервалы: слияние и вставка: с чем путают?

- **Линия развёртки (подсчёт событий)** - Развёртка разбивает интервал на два события и считает их. Слияние держит интервалы целыми.
- **Жадный алгоритм (обменный аргумент)** - Убрать поменьше интервалов это жадный выбор по концу. Слияние просто соединяет пересечения.
- **Сортировка с пользовательским компаратором** - Сортировка по началу это подготовка. Эта страница про проход, который идёт следом.
- **Массив разностей** - Он считает глубину перекрытия в каждой точке. Слияние возвращает интервалы, а не числа.

## Интервалы: слияние и вставка: сложность по времени и памяти

n до 1e6 стоит O(n log n), и всё это сортировка. Проход после неё стоит O(n).

## Интервалы: слияние и вставка: разбор примера

### Вставка интервала в отсортированный список

Дан отсортированный список непересекающихся интервалов и один новый интервал.

Вставьте его, слейте всё, чего он касается, и сохраните порядок без пересечений.

Перенесите все интервалы, которые кончаются до начала нового.

Потом поглотите все пересекающиеся, расширяя новый интервал. Оставшийся хвост перенесите как есть.

```javascript
function insert(intervals, newInterval) {
    const result = [];
    let [start, end] = newInterval;
    let i = 0;

    while (i < intervals.length && intervals[i][1] < start) {
        result.push(intervals[i]); // ends before the new one begins
        i++;
    }

    while (i < intervals.length && intervals[i][0] <= end) {
        start = Math.min(start, intervals[i][0]);
        end = Math.max(end, intervals[i][1]); // the later interval may end sooner
        i++;
    }
    result.push([start, end]);

    while (i < intervals.length) {
        result.push(intervals[i]);
        i++;
    }

    return result;
}
```

## Интервалы: слияние и вставка: частые ошибки

- **Пропускают сортировку** Один проход рассчитывает, что начала только растут. На неотсортированном входе сливаются не те пары.
- **Угадывают знак сравнения** Соприкасаются ли [1, 2] и [2, 3], решает условие задачи. Прочитайте его до выбора оператора.
- **Забывают последний блок** Текущий интервал записывается только после цикла. Без этого в ответе не хватает одного.
- **Берут конец у более позднего интервала** Более поздний интервал может закончиться раньше. Новый конец это максимум из двух.

## Интервалы: слияние и вставка: задачи с собеседований

- **Слияние интервалов** Чистая форма: сортировка по началу и один проход.
- **Вставка интервала** Список уже отсортирован, сливать нужно только середину.
- **Непересекающиеся интервалы** Жадно оставляйте тот, что кончается раньше.
- **Переговорные комнаты** Любое пересечение делает ответ отрицательным.
- **Пересечение двух списков интервалов** Два отсортированных списка обходятся двумя указателями.
- **Свободное время сотрудников** Слейте все занятые блоки и прочитайте промежутки.
- **Удаление вложенных интервалов** Сортируйте по началу, а при равенстве длинный вперёд.

## JavaScript

```javascript
function mergeIntervals(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    const result = [];
    for (const [start, end] of intervals) {
        const last = result[result.length - 1];
        if (last && start <= last[1]) {
            last[1] = Math.max(last[1], end);
        } else {
            result.push([start, end]);
        }
    }
    return result;
}
```

## Python

```python
def merge_intervals(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
```

## PHP

```php
function mergeIntervals(array $intervals): array {
    usort($intervals, fn($a, $b) => $a[0] <=> $b[0]);
    $result = [];
    foreach ($intervals as [$start, $end]) {
        $lastIdx = count($result) - 1;
        if ($lastIdx >= 0 && $start <= $result[$lastIdx][1]) {
            $result[$lastIdx][1] = max($result[$lastIdx][1], $end);
        } else {
            $result[] = [$start, $end];
        }
    }
    return $result;
}
```