---
round: 3
ticket_no: 24
source_no: 12
slug: merge-intervals
topic: Sort
difficulty: Medium
leetcode_id: 56
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 24 — Merge Intervals

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

Дан массив интервалов `intervals`, где `intervals[i] = [start_i, end_i]`. Объедините все пересекающиеся интервалы и верните массив непересекающихся интервалов, который покрывает всё то же множество точек.

```
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]]
```

Constraints: `1 <= intervals.length <= 10^4`; `intervals[i].length == 2`; `0 <= start_i <= end_i <= 10^4`.

## Ответ

> Для начала нужно интервалы отсортировать по первому элементу. А дальше мы начинаем проход по этим интервалам. Берём первый интервал и второй. Нам нужно написать метод, являются ли они пересекающимися. Если они пересекаются, то мы их объединяем. Если не пересекаются, то мы первый интервал в результат уже отправляем. И теперь второй берём за основу и начинаем с ним смотреть. Следующий пересекается — мы их мерджим, и так далее. Ну, как тут надо корректно, так как у нас, че, так как у нас первые, короче, чтобы они пересекались, у нас получается, что начало следующего интервала должно быть меньше или равно, чем завершение предыдущего. Вот такое условие. Ну, а соответственно, слияние интервалов — это просто мы берём у первого первый элемент и максимальный из первого и второго, да, то есть окончание максимальное берём, которое у нас тут есть.

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

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

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

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