Insert Interval

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

A solução de uma única passagem é executada em tempo O(n) : cada intervalo é copiado ou mesclado exatamente uma vez. O resultado contém até n+1 intervalos, portanto ocupa espaço O(n) , e nada mais cresce com a entrada. 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, na qual qualquer intervalo pode se sobrepor a qualquer outro, então é preciso ordenar primeiro. Em Insert Interval, a lista já está ordenada e os intervalos antigos nunca se tocam, então somente o novo intervalo pode desencadear uma mesclagem. Os intervalos com os quais ele se mescla formam uma sequência contínua, e é por isso que uma única passagem sem ordenação é suficiente.

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

Os intervalos [a, b] e [c, d] compartilham pelo menos um ponto exatamente quando a ≤ d e c ≤ b . Isso considera intervalos que se tocam, como [2, 4] e [4, 8] , como sobrepostos, que é o que este problema deseja. Se os intervalos que se tocam tivessem que permanecer separados, você usaria a < d e c < b em vez disso.

Q: É possível tornar Insert Interval mais rápido com busca binária?

A busca binária encontra onde o trecho mesclado começa e termina em O(log n) , porque os inícios e os fins estão ambos ordenados. A função ainda retorna uma nova lista, porém, e copiar para ela os intervalos não alterados custa O(n) . Portanto, o total continua sendo O(n) . A busca binária compensa quando os intervalos ficam em uma estrutura que pode remover e inserir um intervalo sem copiar, como uma árvore balanceada.

MédioIntervalos

+10

Você recebe uma lista de intervalos ordenados por início, fornecida como dois arrays de mesmo tamanho: o intervalo i é [starts[i], ends[i]]. Nenhum par deles se sobrepõe ou se toca. Você também recebe um novo intervalo, [newStart, newEnd]. Insira-o, mescle-o com todos os intervalos com os quais ele se sobrepõe ou se toca e retorne todos os intervalos como um array 2D de pares [start, end], ordenados por início.

Dois 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 em um só. [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 fim de cada intervalo, correspondendo aos inícios
newStartinteger: o início do intervalo a ser inserido
newEndinteger: o fim 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 deles se sobrepõe ou toca outro.
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 como estão.

Entrada: starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
Saída: [[2, 9]]
Explicação: [4, 8] toca [2, 4] no 4 e [8, 9] no 8. O contato conta como sobreposição, então os três se unem 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 intervalo entre 2 e 9 e não toca em nenhum dos vizinhos, então se encaixa entre eles e nada se funde.

+20 testes ocultos ao enviar

Para ir além

Suponha que você insira muitos novos intervalos, um após o outro, na mesma lista. Como você armazenaria os intervalos para que cada inserção custasse O(log n) mais uma etapa para cada 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 já estão separados e em ordem, então só o novo intervalo pode causar uma fusão. Isso divide a lista em três grupos: intervalos que terminam antes de o novo começar, intervalos que se sobrepõem a ele ou o tocam e intervalos que começam depois de ele terminar. Copie o primeiro grupo, combine o grupo do meio em um único intervalo e copie o último grupo. Uma passagem, sem ordenação.

Adicione isso e mescle tudo novamente

Intuição

Se você já resolveu Merge Intervals, pode reutilizá-lo aqui. Insira o novo intervalo na lista, ordene todos os n+1 intervalos pelo início e faça a mesclagem. Depois da ordenação, um intervalo só pode se sobrepor ao grupo imediatamente anterior, então percorra a lista mantendo o último intervalo mesclado. Quando o próximo início for menor ou igual ao fim dele, estenda o fim. Caso contrário, há uma lacuna real, e começa um novo intervalo.

Execute o algoritmo no primeiro exemplo. A lista fica assim: [1, 3], [5, 7], [6, 11], [10, 12], [15, 18]. [1, 3] fica separado, pois 5 é maior que 3. 6 é menor ou igual a 7, então [5, 7] se estende até [5, 11]. 10 é menor ou igual a 11, então o intervalo se estende até [5, 12]. 15 é maior que 12, então [15, 18] inicia um novo intervalo.

Isso está correto e, com 2000 intervalos, é rápido. No entanto, descarta dois fatos que foram informados: a lista já está ordenada, e os intervalos antigos nunca se mesclam entre si. Pagar O(n log n) para reordenar uma lista que está fora de ordem em um único ponto é a etapa que um entrevistador vai pedir para você eliminar.

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, anexe 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 passagem em três partes

Intuição

Percorra a lista uma vez com um índice i e divida-a em três sequências. Primeiro, cada intervalo com ends[i] < newStart termina antes do início do novo, então não compartilha nenhum ponto com ele: copie-o para o resultado. O teste usa < estrito porque um intervalo que termina exatamente em newStart toca o novo e precisa ser mesclado.

Segundo, cada intervalo com starts[i] ≤ mergedEnd se sobrepõe ao intervalo que você está construindo ou o toca. Incorpore-o: mergedStart passa a ser o menor início e mergedEnd, o maior fim. Os intervalos dessa sequência ficam lado a lado, pois a lista está ordenada. Quando um intervalo começa depois de mergedEnd, todos os seguintes começam ainda mais à direita, então nenhum intervalo posterior pode ser mesclado. Acrescente o intervalo mesclado; essa etapa também cobre o caso em que a sequência está vazia e o novo intervalo é inserido sozinho.

Terceiro, copie tudo o que restar. Esses intervalos começam depois do fim do intervalo mesclado e já estavam separados uns dos outros.

Acompanhe o primeiro exemplo. [1, 3] termina antes de 6: copie-o. [5, 7] começa em 5, que é menor ou igual a 11: o intervalo mesclado passa a ser [5, 11]. [10, 12] começa em 10, menor ou igual a 11: ele passa a ser [5, 12]. [15, 18] começa depois de 12, então acrescente [5, 12] e copie [15, 18]. Cada intervalo é examinado uma vez, então o tempo é O(n), e a única memória extra é o próprio 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 prossiga.
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

O loop é curto, então a maioria dos bugs vem de uma comparação incorreta ou de um caso esquecido nas extremidades da lista.

Usar a desigualdade errada 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. Intervalos que se tocam são mesclados, então o primeiro teste é estrito e o segundo não.
Mesclar intervalos que apenas parecem adjacentes. [1, 2] e [3, 4] não compartilham nenhum ponto, então comparar com mergedEnd + 1 une intervalos que deveriam permanecer separados.
Manter newStart como o início do intervalo mesclado. Quando o novo intervalo começa dentro de um intervalo antigo, como [6, 11] dentro de [5, 7], o resultado começa em 5. Use o menor dos dois inícios.
Adicionar o novo intervalo apenas quando ele se sobrepõe a algum intervalo. Quando ele fica antes de todos os intervalos, depois de todos eles ou em uma lacuna, o loop do meio não é executado, e o novo intervalo ainda precisa ser adicionado.
Ler starts[i] ou ends[i] antes de verificar i < n. Quando o novo intervalo ultrapassa o último intervalo, o índice passa do fim dos arrays.

Perguntas frequentes4

Qual é a complexidade de tempo de Insert Interval?

A solução de uma única passagem é executada em tempo O(n): cada intervalo é copiado ou mesclado exatamente uma vez. O resultado contém até n+1 intervalos, portanto ocupa espaço O(n), e nada mais cresce com a entrada. 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, na qual qualquer intervalo pode se sobrepor a qualquer outro, então é preciso ordenar primeiro. Em Insert Interval, a lista já está ordenada e os intervalos antigos nunca se tocam, então somente o novo intervalo pode desencadear uma mesclagem. Os intervalos com os quais ele se mescla formam uma sequência contínua, e é por isso que uma única passagem sem ordenação é suficiente.

Como verificar se dois intervalos se sobrepõem?

Os intervalos [a, b] e [c, d] compartilham pelo menos um ponto exatamente quando a ≤ d e c ≤ b. Isso considera intervalos que se tocam, como [2, 4] e [4, 8], como sobrepostos, que é o que este problema deseja. Se os intervalos que se tocam tivessem que permanecer separados, você usaria a < d e c < b em vez disso.

É possível tornar Insert Interval mais rápido com busca binária?

A busca binária encontra onde o trecho mesclado começa e termina em O(log n), porque os inícios e os fins estão ambos ordenados. A função ainda retorna uma nova lista, porém, e copiar para ela os intervalos não alterados custa O(n). Portanto, o total continua sendo O(n). A busca binária compensa quando os intervalos ficam em uma estrutura que pode remover e inserir um intervalo sem copiar, como uma árvore balanceada.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

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