Напишите функцию, которая принимает массив произвольных интервалов, объединяет любые перекрывающиеся интервалы и возвращает новые интервалы в произвольном порядке.
Каждый интервал состоит из двух целых чисел, где интервал[0] является началом интервала, а интервал[1] — концом интервала. Начало любого конкретного интервала всегда будет меньше или равно концу этого интервала.
Чтобы определить, перекрываются ли два интервала, мы можем проверить, меньше или равно ли текущее начало предыдущему концу (c_start ≤ p_end),если это правда, мы можем объединить оба интервала.
Но наши входные интервалы должны быть в возрастающем порядке, поэтому мы должны отсортировать их по начальным значениям в качестве ключа.
Чтобы отслеживать предыдущий объединенный интервал, вместо того, чтобы искать предыдущий интервал из входного массива, мы должны взять предыдущий интервал из нашего массива результатов, так как конечный элемент в массиве результатов будет нашим последним обновленным интервал.
Если наш текущий интервал может быть объединен с предыдущим интервалом, мы обновляем последний элемент в массиве результатов, в противном случае мы помещаем новый интервал в конец массива результатов.
Код Доступен здесь.
Временная сложность составляет O(n log(n)) + O(n), таким образом, O(n log(n)) — это время, необходимое для сортировки массива.
Сложность пространства составляет O(n), так как мы держим массив результатов.
