Объединение интервалов
Tags: kotlin, algorithms, leetcode, medium
Published: 2022-09-05 04:33:55

Давайте разберем задачу объединения интервалов. Ее можно найти по ссылке [Merge Intervals](https://leetcode.com/problems/merge-intervals/)

## Постановка задачи
Дан массив интервалов `intervals`, где `intervals[i] = [start, end]`. Необходимо объединить все перекрывающиеся интервалы и вернуть массив не перекрывающихся интервалов, который покрывает все интервалы во входных данных.

## Примеры входных данных
### Пример 1
**Входные данные:**
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
**Результат:**
[[1, 6], [8, 10], [15, 18]]
Так как интервалы [1, 3] и [2, 6] пересекаются, мы объединяем их в [1, 6]
### Пример 2
**Входные данные:**
intervals = [[1, 4], [4, 5]]
**Результат:**
[[1, 5]]
Интервалы [1, 4] и [4, 5] пересекаются

## Решение
Нам надо идти по интервалам таким образом, чтобы находить все пересечения. Т.е. сначала необходимо взять самый левый интервал, а потом найти интервалы, пересекающиеся с ним частично или полностью. Если таковые найдутся, то возвращаем новый интервал. Если нет, то записываем исходный интервал в ответ.

## Решение по шагам
**1)** Так как мы не знаем размер выходных данных, то для сохранения результата заведем список, потому что он масштабируется. В конце для ответа преобразуем этот список в массив.

```kotlin
val result: MutableList<IntArray> = mutableListOf()
```

**2)** Отсортируем входные интервалы по стартовому элементу.

```kotlin
val sorted = intervals.sortedBy { it[0] }
```

**3)** Заведем переменные для отслеживания левого и правого конца текущего интервала. В качестве первоначального значения переменных возьмем данные первого интервала. В дальнейшем будем итерироваться со второго элемента входных данных, с индекса 1.

```kotlin
var start: Int = sorted[0][0]
var end: Int = sorted[0][1]
```

**4)** Идем по всем элементам циклом. Достаем левый и правый конец очередного интервала.

```kotlin
var index: Int = 1
while (index < intervals.size) {
   val (eachStart, eachEnd) = sorted[index]
   ...
}
```

**5)** Если левый конец очередного интервала меньше либо равен концу текущего интервала, то интервалы пересекаются. Значит необходимо их объединить, т.е. записать в правый конец текущего интервала, в переменную `end`, значение конца очередного интервала - `eachEnd`.

```kotlin
if (eachStart <= end) {
    end = Math.max(eachEnd, end)
}
```

**6)** Если интервалы не пересекаются, то необходимо записать данные текущего интервала, переменные `eachStart` и `eachEnd` в список ответов. А на их место записываем данные очередного интервала.

```kotlin
if (eachStart <= end) {
    end = Math.max(eachEnd, end)
} else {
    result.add(intArrayOf(start, end))
    start = eachStart
    end = eachEnd
}
```

**7)** После завершения цикла необходимо добавить данные текущего интервала в ответ.

```kotlin
result.add(intArrayOf(start, end))
```

## Оценка сложности
- По времени - O(intervals.length). Мы проходимся по всем входным данным одним циклом.
- По памяти - O(intervals.length). Мы записываем результат в список, который в общем случае линейно растет с количеством входных данных.

## Полное решение
```kotlin
fun merge(intervals: Array<IntArray>): Array<IntArray> {
    val result: MutableList<IntArray> = mutableListOf()
    val sorted = intervals.sortedBy { it[0] }
    var start: Int = sorted[0][0]
    var end: Int = sorted[0][1]
    var index: Int = 1
    while (index < intervals.size) {
        val (eachStart, eachEnd) = sorted[index]
            
        if (eachStart <= end) {
            end = Math.max(eachEnd, end)
        } else {
            result.add(intArrayOf(start, end))
            start = eachStart
            end = eachEnd
        }
        
        index++
    }
    result.add(intArrayOf(start, end))
    return result.toTypedArray()
}
```