Объединение интервалов

#kotlin #algorithms #leetcode #medium

Давайте разберем задачу объединения интервалов. Ее можно найти по ссылке 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) Так как мы не знаем размер выходных данных, то для сохранения результата заведем список, потому что он масштабируется. В конце для ответа преобразуем этот список в массив.

val result: MutableList<IntArray> = mutableListOf()

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

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

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

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

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

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

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

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

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

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

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

result.add(intArrayOf(start, end))

Оценка сложности

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

Полное решение

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()
}