DEV Community

Ivan
Ivan

Posted on

30 17 7 5 4

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

Давайте разберем задачу объединения интервалов. Ее можно найти по ссылке 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()
Enter fullscreen mode Exit fullscreen mode

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

val sorted = intervals.sortedBy { it[0] }
Enter fullscreen mode Exit fullscreen mode

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

var start: Int = sorted[0][0]
var end: Int = sorted[0][1]
Enter fullscreen mode Exit fullscreen mode

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

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

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

if (eachStart <= end) {
    end = Math.max(eachEnd, end)
}
Enter fullscreen mode Exit fullscreen mode

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

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

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

result.add(intArrayOf(start, end))
Enter fullscreen mode Exit fullscreen mode

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

  • По времени - 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()
}
Enter fullscreen mode Exit fullscreen mode

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (2)

Collapse
 
irchiiik profile image
Ирина Лютина

🧐🥲👍

Collapse
 
rkokhan profile image
noman khan
Comment hidden by post author

Some comments have been hidden by the post's author - find out more

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay