---
round: 1
ticket_no: 12
source_no: 12
slug: merge-intervals
topic: Sort
difficulty: Medium
leetcode_id: 56
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-12
---

# Билет 12 — Merge Intervals

## Условие (как предъявлено)

Дан массив интервалов `intervals`, где `intervals[i] = [start_i, end_i]`. Нужно слить все пересекающиеся интервалы и вернуть массив непересекающихся интервалов, покрывающих все входные.

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

Constraints: `1 <= n <= 10^4`, `0 <= start <= end <= 10^4`.

## Ответ

> Я буду исходить из того, что массивы отсортированы по первому элементу по началу. Мы берём первый элемент, первый, ну, смысле, первый диапазон. Первые интервалы. Интервалы отсортированы, короче, в порядке по их стартовой точке. Берём первый интервал и второй интервал и смотрим, у них есть пересечение или нет. Сравниваем конец одного, начало другого, и смотрим. Если пересечения нету, тогда мы первый интервал добавляем в результат. Если пересечение есть, тогда мы как вот создаём новый интервал его. Ну, как бы первый или модифицируем, сливаем их и переходим к следующему интервалу. То есть сравниваем теперь этот новый и третий интервал. И так далее, пока не дойдём до онца.

## Разбор

**Что верно:** один проход со слиянием текущего интервала с последним добавленным и добавлением нового при отсутствии пересечения — верно.

**Что упущено и ошибки:** явно не сказано, что перед проходом нужна сортировка по началу: на входе интервалы не отсортированы, и именно сортировка определяет O(n log n). Не проговорено условие слияния start <= last_end (касание [1,4] и [4,5] сливается). Сложность не названа.

**Эталонная идея:** intervals.sort_by!(&:first); далее один проход: если start <= последний end — расширить end, иначе добавить интервал.

**Сложность:** время O(n log n), память O(n) на результат

**Критерии:** идея ✅ · структура данных ✅ · сложность ⚠️ · граничные случаи ⚠️


**Разбор задачи:** [`../../algo-solutions/01-must-have/03-sort/12-merge-intervals.md`](../../algo-solutions/01-must-have/03-sort/12-merge-intervals.md)