Merge Intervals

Интервал — это диапазон целых чисел с началом и концом. Интервалы, у которых есть хотя бы одна общая точка, объединяются; то же касается интервалов, которые только соприкасаются: [1, 4] и [4, 5] превращаются в [1, 5]. Цель — заменить каждую группу пересекающихся интервалов одним интервалом, охватывающим всю группу.

Секрет — в порядке. После сортировки интервалов по началу всё, что пересекается с интервалом, который вы объединяете, окажется сразу за ним. Пройдите по отсортированному списку, сохраняя последний объединённый интервал: если начало следующего не больше его конца, увеличьте конец; если нет, значит, между ними действительно есть разрыв и начинается новый интервал. Сортировка занимает O(n log n), а проход выполняется за один шаг.

Напишите функцию с именем mergeIntervals, которая принимает два целочисленных массива, starts и ends, и возвращает объединённые интервалы.

Интервалы передаются в виде двух массивов, поскольку не каждый язык здесь принимает двумерный массив в качестве входных данных: интервал i — это [starts[i], ends[i]], и оба массива имеют одинаковую длину. Интервалы не отсортированы.

Объедините все группы пересекающихся интервалов. Интервалы, которые только соприкасаются концами, также считаются пересекающимися. Верните объединённые интервалы в виде двумерного массива [[start, end], ...], отсортированного по началу.

Например, starts = [5, 1, 12, 3] и ends = [7, 4, 14, 6] задают интервалы [5, 7], [1, 4], [12, 14] и [3, 6], которые объединяются в [[1, 7], [12, 14]].

Ограничения: 1 <= starts.length == ends.length <= 10^4, 0 <= starts[i] <= ends[i] <= 10^4.