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

# Билет 08 — Merge Intervals

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

Дан массив интервалов `intervals[i] = [start_i, end_i]`. Объедини все пересекающиеся интервалы и верни массив непересекающихся, покрывающих все исходные. Интервалы `[a,b]` и `[c,d]` пересекаются, если `c <= b`.

```
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`; `0 <= start_i <= end_i <= 10^4`.

## Ответ

> Дословно из `work-08-merge-intervals.md`:

```ruby
def merge(intervals)
  intervals = intervals.sort_by(&:first)

  result = []

  intervals.each do |interval|
    if result.empty?
      result.push interval
      next
    end

    if intersects?(result.last, interval)
      merge!(result.last, interval)
    else
      result.push interval
    end
  end

  result
end

def intersects?(a, b)
  a[1] >= b[0]
end

def merge!(a, b)
  a[1] = [a[1], b[1]]
end

# run O(n)
# mem O(1)
```

## Разбор

**Что верно:**
- Идея каноническая: сортировка по start → линейный проход, мерж с последним результата. Многие не вспоминают про сортировку — это главный инсайт задачи.
- `intersects?` верный: при `a[0] <= b[0]` (сортировка) пересечение ⇔ `a[1] >= b[0]`. ✅
- Мутация `result.last` вместо создания нового интервала — допустимо и компактно.

**Что упущено и ошибки:**
1. ❌ **`merge!` без `.max`:** `a[1] = [a[1], b[1]]` превращает конец в массив `[3,6]`, а не в максимум. Дальше либо `NoMethodError: '>=' for Array`, либо мусор `[[1,[4,5]]]`. Правильно: `a[1] = [a[1], b[1]].max`.
2. ❌ **Время O(n) неверно: O(n log n)** — сортировка `sort_by` доминирует над линейным проходом.
3. ❌ **Память O(1) неверно: O(n)** — `sort_by` даёт копию (O(n)) + result до n интервалов (O(n) на выход).
4. ⚠️ Edge cases не названы: одиночный интервал, примыкающие `[1,4]+[4,5]` (объединяются: `c <= b`), вложенные `[1,10]+[2,3]` (end не сужается — максимум), одинаковые start, дубликаты.

**Эталонная идея:**
Отсортировать по `start`. Идти по интервалам, сравнивая с последним в результате: если `last[1] >= cur[0]` — расширить `last[1] = max(last[1], cur[1])` (только максимум, никогда не сужать); иначе — добавить `cur` как новый. Один проход после сортировки.

**Время:** O(n log n) — сортировка; проход O(n).

**Память:** O(n) — `sort_by` (копия) + результат. Отдельно: выход O(n).

**Граничные случаи:** 1) один интервал → сам себе; 2) примыкающие `[1,4],[4,5]` → `[1,5]` (пересечение включая границу `c <= b`); 3) вложенный `[1,10],[2,3]` → `[1,10]`, end берём максимум; 4) равные start-ы; 5) уже отсортированный или обратный порядок входа — сортировка всё выравнивает.

**Критерии (финально):** идея ✅ · структура данных ✅ · сложность ✅ (O(n log n)/O(n) исправлены) · граничные случаи ❌

## Пересдача (после фикса)

Исправлен `merge!`: `a[1] = [a[1], b[1]].max` (было — присваивание массива вместо максимума, NoMethodError/мусор). Сложности исправлены на O(n log n) / O(n). Прогон: 9/9 OK, включая неотсортированный вход, примыкающие и вложенные интервалы, дубликаты.

Не закрыто: edge cases в ответе не названы — системный пробел раунда.

**Канон сложности:** 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)