Insert Interval

Q: Qual é a complexidade de tempo de Insert Interval?

A solução de passagem única é executada em tempo O(n) , já que cada intervalo é copiado ou incorporado uma vez, e usa espaço O(n) para um resultado de até n+1 intervalos. Adicionar o intervalo e ordenar novamente leva O(n log n) .

Q: Em que Insert Interval é diferente de Merge Intervals?

Merge Intervals começa com uma lista não ordenada, em que qualquer intervalo pode se sobrepor a qualquer outro, então primeiro a ordena. Aqui, a lista está ordenada e os intervalos antigos nunca se tocam, então apenas o novo intervalo pode desencadear uma mesclagem, e os intervalos com os quais ele se mescla formam uma sequência contínua. Uma única passagem é suficiente.

Q: Como verificar se dois intervalos se sobrepõem?

[a, b] e [c, d] compartilham um ponto exatamente quando a ≤ d e c ≤ b . Isso conta intervalos que se tocam, como [2, 4] e [4, 8] , como sobrepostos, conforme este problema exige. Para manter separados os intervalos que se tocam, use a < d e c < b .

MédioIntervalos

+10

Você recebe intervalos ordenados pelo início em dois arrays: o intervalo i é [starts[i], ends[i]], e não há dois intervalos que se sobreponham ou se toquem. Insira o novo intervalo [newStart, newEnd], mescle-o com todos os intervalos com os quais ele se sobrepõe ou se toca e retorne todos os intervalos como pares [start, end] ordenados pelo início.

Os intervalos se tocam quando um termina onde o outro começa, como acontece com [2, 4] e [4, 8], e intervalos que se tocam são mesclados. [1, 2] e [3, 4] não compartilham nenhum ponto, então permanecem separados.

Função

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

startsinteger-array: o início de cada intervalo, em ordem crescente
endsinteger-array: o final de cada intervalo, correspondendo aos inícios
newStartinteger: o início do intervalo a ser inserido
newEndinteger: o final do intervalo a inserir
Retornainteger-2d-array: os intervalos após a inserção como pares [start, end], ordenados por start

Restrições

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: os intervalos estão ordenados pelo início, e nenhum par deles se sobrepõe ou se toca.
0 ≤ newStart ≤ newEnd ≤ 10⁵

Exemplos

Entrada: starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
Saída: [[1, 3], [5, 12], [15, 18]]
Explicação: [6, 11] se sobrepõe a [5, 7] e [10, 12], então os três se tornam [5, 12]. [1, 3] termina antes de 6 e [15, 18] começa depois de 12, então ambos permanecem.

Entrada: starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
Saída: [[2, 9]]
Explicação: [4, 8] toca [2, 4] em 4 e [8, 9] em 8, então os três se juntam em [2, 9].

Entrada: starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
Saída: [[1, 2], [5, 6], [9, 10]]
Explicação: [5, 6] fica no espaço entre 2 e 9 e não toca em nenhum dos vizinhos, então se encaixa entre eles e nada se mescla.

Para ir além

Se você inserir muitos intervalos um após o outro, como os armazenaria para que cada inserção custe O(log n) mais uma etapa por intervalo antigo que ela absorve?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Os intervalos antigos estão ordenados e separados, então apenas o novo intervalo pode causar uma fusão. Isso divide a lista em três grupos: intervalos que terminam antes de ele começar, intervalos que se sobrepõem ou se encostam nele e intervalos que começam depois que ele termina. Copie o primeiro grupo, incorpore o grupo do meio em um único intervalo e copie o último. Uma passagem, sem ordenação.

Adicione isso e mescle tudo novamente

Intuição

Reutilize a mesclagem de intervalos: adicione o novo intervalo, ordene os n+1 intervalos pelo início e percorra-os mantendo o último intervalo mesclado. Após a ordenação, um intervalo só pode se sobrepor ao grupo imediatamente anterior a ele; assim, quando o próximo início for menor ou igual ao fim mantido, estenda o fim; caso contrário, abre-se uma lacuna e começa um novo intervalo.

A ordenação custa O(n log n) para corrigir uma lista que está fora de ordem em um ponto, e ignora que os intervalos antigos nunca se mesclam entre si.

Algoritmo

Associe cada início ao seu fim e adicione [newStart, newEnd] à lista.
Ordene os intervalos pelo início.
Percorra-os em ordem, mantendo o último intervalo mesclado.
Se o próximo início for menor ou igual ao fim mantido, atualize o fim mantido para o maior dos dois fins.
Caso contrário, acrescente o próximo intervalo como um novo intervalo mesclado. Retorne a lista mesclada.

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

Uma passada em três partes

Intuição

A lista está ordenada e seus intervalos estão separados, então os intervalos que se encontram com o novo formam uma sequência contínua. Tudo antes dessa sequência tem ends[i] < newStart: termina antes de o novo intervalo começar. O teste é estrito porque um intervalo que termina exatamente em newStart toca o novo e deve ser mesclado.

Dentro da sequência, um intervalo com starts[i] ≤ mergedEnd se sobrepõe ao intervalo que você está construindo ou o toca, então ele o amplia para o menor início e o maior fim. O primeiro intervalo que começa depois de mergedEnd encerra a sequência, pois todos os seguintes começam mais à direita. Quando a sequência está vazia, o novo intervalo é inserido sozinho. No primeiro exemplo, [1, 3] é copiado, [5, 7] e [10, 12] ampliam [6, 11] para [5, 12], e [15, 18] é copiado. Cada intervalo é analisado uma vez: tempo O(n) e nenhuma memória além da necessária para o resultado.

Algoritmo

Copie os intervalos para o resultado enquanto ends[i] < newStart.
Defina mergedStart = newStart e mergedEnd = newEnd.
Enquanto starts[i] ≤ mergedEnd, defina mergedStart como o menor início e mergedEnd como o maior fim e avance.
Adicione [mergedStart, mergedEnd].
Copie os intervalos restantes e retorne o resultado.

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

Armadilhas e casos extremos

Desigualdades incorretas para intervalos que se tocam. Com ends[i] ≤ newStart no primeiro loop, ou starts[i] < mergedEnd no segundo, [2, 4] e [4, 8] permanecem separados. O primeiro teste é estrito, o segundo não.
Comparar com mergedEnd + 1. Isso une [1, 2] e [3, 4], que não compartilham nenhum ponto.
Manter newStart como o início do intervalo mesclado. [6, 11] começa dentro de [5, 7], então o resultado começa em 5.
Adicionar o novo intervalo apenas quando ele se sobrepõe a algum intervalo. Quando ele fica em uma lacuna ou além de uma das extremidades, como acontece com [5, 6], o loop do meio nunca é executado, mas ele ainda precisa ser adicionado.
Ler starts[i] antes de verificar i < n. Um novo intervalo que ultrapassa o último faz o índice sair dos limites.

Perguntas frequentes3

Qual é a complexidade de tempo de Insert Interval?

A solução de passagem única é executada em tempo O(n), já que cada intervalo é copiado ou incorporado uma vez, e usa espaço O(n) para um resultado de até n+1 intervalos. Adicionar o intervalo e ordenar novamente leva O(n log n).

Em que Insert Interval é diferente de Merge Intervals?

Merge Intervals começa com uma lista não ordenada, em que qualquer intervalo pode se sobrepor a qualquer outro, então primeiro a ordena. Aqui, a lista está ordenada e os intervalos antigos nunca se tocam, então apenas o novo intervalo pode desencadear uma mesclagem, e os intervalos com os quais ele se mescla formam uma sequência contínua. Uma única passagem é suficiente.

Como verificar se dois intervalos se sobrepõem?

[a, b] e [c, d] compartilham um ponto exatamente quando a ≤ d e c ≤ b. Isso conta intervalos que se tocam, como [2, 4] e [4, 8], como sobrepostos, conforme este problema exige. Para manter separados os intervalos que se tocam, use a < d e c < b.

def insertInterval(starts, ends, newStart, newEnd):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada

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