---
title: Merge Intervals
difficulty: Medium
category: Sort
leetcode_id: 56
revision_count: 1
last_revision: 2026-09-12
---

# Merge Intervals

> **LeetCode:** [#56](https://leetcode.com/problems/merge-intervals/)
> **Сложность:** Medium
> **Категория:** Sort

## Условие

Дан массив интервалов `intervals[i] = [startᵢ, endᵢ]`. Объединить все пересекающиеся интервалы и вернуть массив непересекающихся.

```
Input:  intervals = [[1,3],[2,6],[8,10],[15,18]] → Output: [[1,6],[8,10],[15,18]]
Input:  intervals = [[1,4],[4,5]]                → Output: [[1,5]]
```

## Ключевая идея

**Метафора.** Интервалы — это отрезки на числовой прямой. Нарисуй их все: пересекающиеся отрезки «склеиваются» в один длинный. Задача — пройти по прямой слева направо и склеить всё, что соприкасается.

**Шаг 1 — отсортировать по началу (`start`).** Зачем: только после сортировки пересечения становятся «соседними». Любые два пересекающихся интервала окажутся рядом в отсортированном порядке, поэтому их можно обрабатывать подряд.

**Шаг 2 — один проход, сравнивая каждый интервал только с последним объединённым.** Это и есть ключевой трюк: не нужно сравнивать каждый с каждым (O(n²) не нужен). После сортировки текущий интервал может пересечься **только** с самым правым из уже объединённых — потому что у него наибольший `end` среди них. Если текущий не пересекается с ним (`start > last_end`), то он тем более не пересекается ни с одним более ранним (их концы ещё меньше).

**Два случая на каждом шаге:**

1. `cur.start <= last.end` — соприкасаются → растягиваем последний: `last.end = max(last.end, cur.end)`. `max` обязателен: вложенный интервал `[1,10]` + `[2,3]` не должен «съесть» конец `10`.
2. `cur.start > last.end` — между ними зазор → начинаем новый интервал, добавляем его в результат.

**Инвариант (почему это корректно):** `last` — это самый правый край всего, что мы уже склеили. Все предыдущие интервалы целиком лежат левее или внутри `last`, поэтому про них можно забыть и помнить только `last`.

## Оценка сложности

- **Время:** O(n log n) — сортировка
- **Память:** O(n) — хранение результата (или O(1) если сортировка in-place и мержить прямо во входном массиве)

## Решение (Ruby)

```ruby
# @param {Integer[][]} intervals
# @return {Integer[][]}
def merge(intervals)
  return [] if intervals.empty?

  sorted = intervals.sort_by(&:first)
  merged = [sorted[0]]

  sorted[1..].each do |interval|
    last = merged[-1]

    if interval[0] <= last[1]
      # пересечение — расширяем конец
      last[1] = [last[1], interval[1]].max
    else
      merged << interval
    end
  end

  merged
end
```

## Разбор на примере

```
intervals = [[1,3],[2,6],[8,10],[15,18]]

Числовая прямая (как это выглядит):

  1   3
  [===]
   2     6
   [=====]      ← [2,6] задевает [1,3], склеиваются
                8   10
                [===]
                       15    18
                       [=====]

Шаг 0: Сортируем по start → [[1,3],[2,6],[8,10],[15,18]]
Шаг 1: merged = [[1,3]]
Шаг 2: [2,6]: 2 <= 3 (соприкасаются) → merged[-1] = [1, max(3,6)] = [1,6]
Шаг 3: [8,10]: 8 > 6 (зазор) → новый интервал → merged = [[1,6],[8,10]]
Шаг 4: [15,18]: 15 > 10 (зазор) → новый интервал → merged = [[1,6],[8,10],[15,18]]

Result: [[1,6],[8,10],[15,18]]
```

## Edge Cases

- **Пустой массив**: [] → [] (должен быть явный guard clause)
- **Один интервал**: [[1,5]] → [[1,5]] (цикл не выполняется)
- **Все пересекаются**: [[1,2],[1,3],[2,5]] → [[1,5]] (последовательные мержи)
- **Ни одного пересечения**: [[1,2],[3,4],[5,6]] → без изменений
- **Вложенные интервалы**: [[1,10],[2,3],[4,5]] → [[1,10]] (максимальный конец)
- **Граничное пересечение**: [[1,4],[4,5]] → [[1,5]] (условие ≤, а не <)
- **Неотсортированный вход**: [[2,6],[1,3],[15,18],[8,10]] → сортировка отрабатывает

## Типичные ошибки

1. ❌ **Не отсортировать вход** — без сортировки проход не работает.
2. ❌ **Использовать `<` вместо `<=` для проверки пересечения** — пропускает случай [1,4],[4,5] (конец в начале следующего).
3. ❌ **Не обновлять `end` при вложенности**: `last[1] = interval[1]` вместо `max` — теряет конец когда предыдущий интервал шире.
4. ❌ **Guard clause через `return intervals` вместо `return []`** — при пустом входе неверно возвращает nil или пустой массив (зависит от языка/ожиданий).

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Brute-force (проверка всех пар) | O(n²) | O(n) | Не нужен — сортировка дешевле |
| **Sort + merge** | **O(n log n)** | **O(n)** | **финальное решение** |

Sort + merge — единственный разумный подход. Сортировка — bottleneck, её не обойти.

## Заметки после повторения

_— Заполняется после каждой тренировки._