Давайте разберем задачу объединения интервалов. Ее можно найти по ссылке Объединить интервалы


Постановка задач

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


Примеры входных данных


Пример 1

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


Пример 2

Входные данные:
интервалы = [[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()
}
Войти в полноэкранный режим

Выйти из полноэкранного режима