Merge Intervals

Q: Какова временная сложность задачи объединения интервалов?

Решение с сортировкой и проходом работает за время O(n log n) для n интервалов: сортировка занимает O(n log n), а проход — O(n). Для отсортированных пар и результата используется O(n) дополнительной памяти.

Q: Почему интервалы сортируют по началу, а не по концу?

При сортировке по началу интервал может пересекаться только с группой, которую вы строите, поэтому одного сравнения с концом этой группы достаточно, чтобы всё решить. При сортировке по концу более поздний интервал может начинаться раньше групп, которые вы уже закрыли: [5, 6] идёт перед [1, 10] , и при проходе вперёд мы ошибочно оставили бы 5 в качестве начала.

Q: Можешь ли ты объединить интервалы без дополнительного пространства?

Да, если можно изменить входные данные. Отсортируй интервалы на месте, затем записывай каждый объединённый интервал в начало того же массива и сохраняй индекс последнего записанного интервала. Время остаётся O(n log n), а дополнительная память ограничивается той, которую использует сортировка в твоём языке.

СреднеИнтервалы Сортировка

+10

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

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

Функция

mergeIntervals(starts: integer-array, ends: integer-array) → integer-2d-array

startsinteger-array: начало каждого интервала
endsinteger-array: конец каждого интервала, с тем же индексом, что и его начало
Возвращаетinteger-2d-array: объединённые интервалы в виде пар [start, end], отсортированные по началу

Ограничения

1 ≤ starts.length == ends.length ≤ 10⁴
0 ≤ starts[i] ≤ ends[i] ≤ 10⁴
Интервалы поступают в произвольном порядке.
Интервалы, которые только соприкасаются концами, считаются пересекающимися.

Примеры

Ввод: starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
Вывод: [[1, 7], [12, 14]]
Пояснение: В порядке начала [1, 4] перекрывается с [3, 6], который перекрывается с [5, 7], поэтому три интервала объединяются в [1, 7]. [12, 14] начинается после 7 и остаётся отдельно.

Дополнительный вопрос

Интервалы уже объединены и отсортированы по началу, и тебе нужно добавить один новый интервал. Сможешь вернуть объединённый список за время O(n), не выполняя сортировку повторно?

Решение

Объединение пар в произвольном порядке требует повторных проходов, потому что каждое объединение расширяет интервал и позволяет ему достигнуть интервалов, которые вы уже проверили. Вместо этого отсортируйте интервалы по началу. Тогда интервал может пересекаться только с формируемой группой, и одного прохода будет достаточно.

Объединяйте пересекающиеся пары, пока ничего не меняется

Верно, но не успевает на самых больших тестах

Идея

Интервалы [a, b] и [c, d] пересекаются, если c ≤ b и a ≤ d, а [min(a, c), max(b, d)] охватывает оба интервала. При каждом объединении удаляется один интервал, поэтому процесс завершается, а когда за полный проход не обнаруживается пересечений, никакие два оставшихся интервала не имеют общих точек. Одного прохода недостаточно: объединённый интервал становится шире и теперь может достигать интервала, с которым его меньшую часть сравнивали ранее в ходе прохода.

За один проход сравнивается около n²/2 пар, и может потребоваться до n проходов: O(n³). Один проход по 10^4 интервалам — это уже 5 × 10^7 сравнений.

Алгоритм

Скопируй starts и ends и веди счётчик n активных интервалов.
Сравни каждый интервал i со всеми следующими интервалами j. Если они пересекаются, расширь i, чтобы он охватывал j, перемести последний активный интервал в ячейку j и уменьши n на единицу.
После объединения снова проверь ячейку j, поскольку теперь в ней находится другой интервал.
Повторяй проходы, пока один из них не завершится без объединений.
Сопоставь каждой активной начальной точке её конечную точку, отсортируй пары по начальным точкам и верни их.

def mergeIntervals(starts, ends):
    s = list(starts)
    e = list(ends)
    n = len(s)
    changed = True
    while changed:
        changed = False
        i = 0
        while i < n:
            j = i + 1
            while j < n:
                if s[j] <= e[i] and s[i] <= e[j]:
                    # Intervals i and j overlap: interval i absorbs interval j.
                    s[i] = min(s[i], s[j])
                    e[i] = max(e[i], e[j])
                    # Move the last interval into slot j and drop the last slot.
                    n -= 1
                    s[j] = s[n]
                    e[j] = e[n]
                    changed = True
                else:
                    j += 1
            i += 1
    return sorted([s[k], e[k]] for k in range(n))

Отсортируйте по началу и пройдите один раз

Идея

После сортировки по началу следующий интервал начинается не раньше любого интервала в последней группе, которая заканчивается в e. Если его начало не позже e, он пересекается с группой или соприкасается с ней и присоединяется к ней, а e становится большим из двух концов. Если его начало дальше e, ни один последующий интервал тоже не сможет вернуться к этой группе, потому что последующие интервалы начинаются правее. Группа завершена, и интервал открывает новую.

Сортировка требует O(n log n), а алгоритм прохода посещает каждый интервал один раз. Группы закрываются слева направо, поэтому результат получается отсортированным по началу.

Алгоритм

Сопоставьте каждому началу его конец: интервал i — это [starts[i], ends[i]].
Отсортируйте пары по началу.
Пройдите по отсортированным парам. Если результат пуст или пара начинается после конца последнего объединённого интервала, добавьте пару как новый интервал.
В противном случае установите конец последнего объединённого интервала равным большему из его конца и конца пары.
Верните объединённый список.

def mergeIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            if end > merged[-1][1]:
                merged[-1][1] = end
        else:
            merged.append([start, end])
    return merged

Ловушки и крайние случаи

Сравнение с помощью < вместо ≤. Соприкасающиеся интервалы, например [1, 4] и [4, 5], нужно объединять.
Присваивание конца нового интервала вместо большего из двух значений. После [1, 10] интервал [2, 3] должен оставить результат [1, 10].
Сортировка starts отдельно с последующим чтением ends по новым позициям, из-за чего начало связывается с концом другого интервала. Сначала объедините их в пары или отсортируйте индексы.
Сравнение с предыдущим входным интервалом вместо последнего объединённого. В последовательности [1, 10], [2, 3], [4, 5] третий интервал находится внутри [1, 10], хотя он не соприкасается с [2, 3].
В C не присваивать *returnSize значение, равное числу объединённых интервалов, и не устанавливать размер каждого столбца равным 2.

Частые вопросы3

Какова временная сложность задачи объединения интервалов?

Решение с сортировкой и проходом работает за время O(n log n) для n интервалов: сортировка занимает O(n log n), а проход — O(n). Для отсортированных пар и результата используется O(n) дополнительной памяти.

Почему интервалы сортируют по началу, а не по концу?

При сортировке по началу интервал может пересекаться только с группой, которую вы строите, поэтому одного сравнения с концом этой группы достаточно, чтобы всё решить. При сортировке по концу более поздний интервал может начинаться раньше групп, которые вы уже закрыли: [5, 6] идёт перед [1, 10], и при проходе вперёд мы ошибочно оставили бы 5 в качестве начала.

Можешь ли ты объединить интервалы без дополнительного пространства?

Да, если можно изменить входные данные. Отсортируй интервалы на месте, затем записывай каждый объединённый интервал в начало того же массива и сохраняй индекс последнего записанного интервала. Время остаётся O(n log n), а дополнительная память ограничивается той, которую использует сортировка в твоём языке.

def mergeIntervals(starts, ends):
    # Напишите код здесь

Тест #1

Тест #2

Аргументы

starts = [5, 1, 12, 3]
ends = [7, 4, 14, 6]

Ожидаемый вывод

[[1, 7], [12, 14]]