Insert Interval

Q: Какова временная сложность алгоритма Insert Interval?

Решение за один проход работает за время O(n) , поскольку каждый интервал копируется или объединяется ровно один раз, и использует O(n) памяти для результата, содержащего до n+1 интервалов. Добавление интервала и повторная сортировка занимают O(n log n) .

Q: Чем задача Insert Interval отличается от задачи Merge Intervals?

Задача Merge Intervals начинается с неотсортированного списка, в котором любой интервал может пересекаться с любым другим, поэтому сначала список сортируют. Здесь список отсортирован, а старые интервалы никогда не соприкасаются, поэтому слияние может запустить только новый интервал, и интервалы, с которыми он объединяется, образуют один непрерывный участок. Достаточно одного прохода.

Q: Как проверить, пересекаются ли два интервала?

[a, b] и [c, d] имеют общую точку тогда и только тогда, когда a ≤ d и c ≤ b . Так соприкасающиеся интервалы, например [2, 4] и [4, 8] , считаются пересекающимися, как и требуется в этой задаче. Чтобы соприкасающиеся интервалы не пересекались, используйте a < d и c < b .

СреднеИнтервалы

+10

Тебе даны интервалы, отсортированные по началу, в виде двух массивов: интервал i — это [starts[i], ends[i]], и никакие два интервала не перекрываются и не соприкасаются. Вставь новый интервал [newStart, newEnd], объедини его со всеми интервалами, которые он перекрывает или которых касается, и верни все интервалы в виде пар [start, end], отсортированных по началу.

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

Функция

insertInterval(starts: integer-array, ends: integer-array, newStart: integer, newEnd: integer) → integer-2d-array

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

Ограничения

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: интервалы отсортированы по началу, и никакие два из них не пересекаются и не соприкасаются.
0 ≤ newStart ≤ newEnd ≤ 10⁵

Примеры

Ввод: starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
Вывод: [[1, 3], [5, 12], [15, 18]]
Пояснение: [6, 11] пересекается с [5, 7] и [10, 12], поэтому все три объединяются в [5, 12]. [1, 3] заканчивается до 6, а [15, 18] начинается после 12, поэтому оба интервала остаются без изменений.

Ввод: starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
Вывод: [[2, 9]]
Пояснение: [4, 8] соприкасается с [2, 4] в точке 4 и с [8, 9] в точке 8, поэтому все три объединяются в [2, 9].

Ввод: starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
Вывод: [[1, 2], [5, 6], [9, 10]]
Пояснение: [5, 6] находится в промежутке между 2 и 9 и не касается ни одного из соседних отрезков, поэтому он вставляется между ними, и ничего не объединяется.

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

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

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Старые интервалы отсортированы и не пересекаются, поэтому объединение может вызвать только новый интервал. Это делит список на три группы: интервалы, которые заканчиваются до его начала, интервалы, которые пересекаются с ним или соприкасаются с ним, и интервалы, которые начинаются после его окончания. Скопируй первую группу, объедини интервалы средней группы в один, скопируй последнюю. Один проход, без сортировки.

Добавь это и снова объедини всё

Идея

Повторное использование слияния интервалов: добавь новый интервал, отсортируй все n+1 интервалов по началу и пройди по ним, удерживая последний объединённый интервал. После сортировки интервал может пересекаться только с группой непосредственно перед ним, поэтому, если начало следующего интервала не позже конца удерживаемого, растяни конец; иначе образуется промежуток и начинается новый интервал.

Сортировка требует O(n log n), чтобы исправить список, в котором порядок нарушен в одном месте, и не учитывает, что старые интервалы никогда не объединяются друг с другом.

Алгоритм

Сопоставь каждое начало с его концом и добавь [newStart, newEnd] в список.
Отсортируй интервалы по началу.
Просматривай их по порядку, сохраняя последний объединённый интервал.
Если следующее начало не больше сохранённого конца, установи сохранённый конец равным большему из двух концов.
Иначе добавь следующий интервал как новый объединённый интервал. Верни объединённый список.

def insertInterval(starts, ends, newStart, newEnd):
    intervals = list(zip(starts, ends))
    intervals.append((newStart, newEnd))
    intervals.sort()
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)  # overlaps or touches: stretch
        else:
            merged.append([start, end])  # a real gap: a new interval begins
    return merged

Один проход из трёх частей

Идея

Список отсортирован, а его интервалы не пересекаются, поэтому интервалы, которые соприкасаются с новым, образуют одну непрерывную последовательность. Все интервалы до этой последовательности удовлетворяют условию ends[i] < newStart: они заканчиваются до начала нового интервала. Условие строгое, потому что интервал, который заканчивается ровно в newStart, соприкасается с новым и должен объединиться с ним.

Внутри этой последовательности интервал, для которого starts[i] ≤ mergedEnd, пересекается или соприкасается с интервалом, который ты строишь, поэтому он расширяет его: начало становится меньше, а конец — больше. Первый интервал, который начинается после mergedEnd, завершает последовательность, поскольку каждый следующий интервал начинается ещё правее. Если последовательность пуста, новый интервал добавляется отдельно. В первом примере [1, 3] копируется, [5, 7] и [10, 12] расширяют [6, 11] до [5, 12], а [15, 18] копируется. Каждый интервал рассматривается один раз: время O(n), память не требуется, кроме памяти для результата.

Алгоритм

Скопируй интервалы в результат, пока ends[i] < newStart.
Установи mergedStart = newStart и mergedEnd = newEnd.
Пока starts[i] ≤ mergedEnd, установи для mergedStart меньшее начало, а для mergedEnd — больший конец, затем переходи дальше.
Добавь [mergedStart, mergedEnd].
Скопируй оставшиеся интервалы и верни результат.

def insertInterval(starts, ends, newStart, newEnd):
    n = len(starts)
    result = []
    i = 0
    # 1. Intervals that end before the new one starts stay as they are.
    while i < n and ends[i] < newStart:
        result.append([starts[i], ends[i]])
        i += 1
    # 2. Intervals that overlap or touch the new one fold into it.
    mergedStart, mergedEnd = newStart, newEnd
    while i < n and starts[i] <= mergedEnd:
        mergedStart = min(mergedStart, starts[i])
        mergedEnd = max(mergedEnd, ends[i])
        i += 1
    result.append([mergedStart, mergedEnd])
    # 3. Intervals that start after the merged one ends stay as they are.
    while i < n:
        result.append([starts[i], ends[i]])
        i += 1
    return result

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

Неверные неравенства для соприкасающихся интервалов. При ends[i] ≤ newStart в первом цикле или starts[i] < mergedEnd во втором цикле [2, 4] и [4, 8] остаются раздельными. Первое условие должно быть строгим, а второе — нет.
Сравнение с mergedEnd + 1. Это объединяет [1, 2] и [3, 4], у которых нет общих точек.
Сохранение newStart в качестве начала объединённого интервала. [6, 11] начинается внутри [5, 7], поэтому результат начинается с 5.
Добавление нового интервала только при пересечении с другим интервалом. Если он попадает в промежуток или находится за пределами интервалов, как [5, 6], средний цикл не выполнится, но интервал всё равно нужно добавить.
Чтение starts[i] до проверки i < n. Если новый интервал выходит за пределы последнего интервала, индекс выходит за границы массива.

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

Какова временная сложность алгоритма Insert Interval?

Решение за один проход работает за время O(n), поскольку каждый интервал копируется или объединяется ровно один раз, и использует O(n) памяти для результата, содержащего до n+1 интервалов. Добавление интервала и повторная сортировка занимают O(n log n).

Чем задача Insert Interval отличается от задачи Merge Intervals?

Задача Merge Intervals начинается с неотсортированного списка, в котором любой интервал может пересекаться с любым другим, поэтому сначала список сортируют. Здесь список отсортирован, а старые интервалы никогда не соприкасаются, поэтому слияние может запустить только новый интервал, и интервалы, с которыми он объединяется, образуют один непрерывный участок. Достаточно одного прохода.

Как проверить, пересекаются ли два интервала?

[a, b] и [c, d] имеют общую точку тогда и только тогда, когда a ≤ d и c ≤ b. Так соприкасающиеся интервалы, например [2, 4] и [4, 8], считаются пересекающимися, как и требуется в этой задаче. Чтобы соприкасающиеся интервалы не пересекались, используйте a < d и c < b.

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

Тест #1

Тест #2

Тест #3

Аргументы

starts = [1, 5, 10, 15]
ends = [3, 7, 12, 18]
newStart = 6
newEnd = 11

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

[[1, 3], [5, 12], [15, 18]]