# Билет 08 — рабочий лист

## Условие

Дан массив интервалов `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`.

## Решение — пиши здесь

```ruby
#
# Твоя реализация. Не забудь: проговаривай (пиши в комментариях) —
# 1) идею, 2) сложность по времени, 3) сложность по памяти,
# 4) граничные случаи.
#

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]].max
end
```

run O(n log n)

mem O(n)