Insert Interval

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

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

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

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

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

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

Q: Может ли бинарный поиск ускорить вставку интервала?

Бинарный поиск находит, где начинается и заканчивается объединённый диапазон, за O(log n) , поскольку начала и концы отсортированы. Однако функция по-прежнему возвращает новый список, а копирование в него нетронутых интервалов требует O(n) . Поэтому общая сложность остаётся O(n) . Бинарный поиск даёт преимущество, когда интервалы хранятся в структуре, которая может удалять и вставлять диапазон без копирования, например в сбалансированном дереве.

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

+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 и не соприкасается ни с одним из соседних интервалов, поэтому он вставляется между ними, и ничего не объединяется.

+20 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

Идея

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

Проследи за алгоритмом на первом примере. Список становится таким: [1, 3], [5, 7], [6, 11], [10, 12], [15, 18]. [1, 3] остаётся отдельно, поскольку 5 больше 3. 6 меньше или равно 7, поэтому [5, 7] растягивается до [5, 11]. 10 меньше или равно 11, поэтому интервал растягивается до [5, 12]. 15 больше 12, поэтому [15, 18] начинает новый интервал.

Это решение правильное и быстро работает даже с 2000 интервалами. Но оно не учитывает два известных тебе факта: список уже отсортирован, а старые интервалы никогда не пересекаются друг с другом. Тратить 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

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

Идея

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

Затем каждый интервал, для которого starts[i] ≤ mergedEnd, перекрывает интервал, который вы строите, или касается его. Объедините его с ним: mergedStart становится меньшим из начал, а mergedEnd — большим из концов. Интервалы в этой группе идут друг за другом, потому что список отсортирован. Как только интервал начинается после mergedEnd, все следующие начинаются ещё правее, поэтому ни один из них уже не сможет объединиться. Добавьте объединённый интервал; этот шаг также охватывает случай, когда группа пуста и новый интервал добавляется отдельно.

В-третьих, скопируйте всё, что осталось. Эти интервалы начинаются после конца объединённого интервала и уже не пересекаются друг с другом.

Проследите за первым примером. [1, 3] заканчивается до 6: скопируйте его. [5, 7] начинается в точке 5, которая не больше 11: объединённый интервал становится [5, 11]. [10, 12] начинается в точке 10, которая не больше 11: он становится [5, 12]. [15, 18] начинается после 12, поэтому добавьте [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] остаются раздельными. Соприкасающиеся интервалы объединяются, поэтому первое условие должно быть строгим, а второе — нет.
Объединение интервалов, которые только кажутся соседними. [1, 2] и [3, 4] не имеют общих точек, поэтому сравнение с mergedEnd + 1 объединяет интервалы, которые должны оставаться раздельными.
Сохранение newStart в качестве начала объединённого интервала. Когда новый интервал начинается внутри старого, как [6, 11] внутри [5, 7], результат начинается с 5. Выберите меньшее из двух начал.
Добавление нового интервала только в том случае, если он пересекается с каким-либо интервалом. Если он находится перед всеми интервалами, после всех интервалов или в промежутке, средний цикл не выполняется, но новый интервал всё равно нужно добавить.
Чтение starts[i] или ends[i] до проверки i < n. Когда новый интервал выходит за пределы последнего интервала, индекс выходит за границы массивов.

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

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

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

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

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

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

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

Может ли бинарный поиск ускорить вставку интервала?

Бинарный поиск находит, где начинается и заканчивается объединённый диапазон, за O(log n), поскольку начала и концы отсортированы. Однако функция по-прежнему возвращает новый список, а копирование в него нетронутых интервалов требует O(n). Поэтому общая сложность остаётся O(n). Бинарный поиск даёт преимущество, когда интервалы хранятся в структуре, которая может удалять и вставлять диапазон без копирования, например в сбалансированном дереве.

Python

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]]