Merge Intervals

Q: Qual é a complexidade de tempo de Merge Intervals?

A solução de ordenação e varredura é executada em tempo O(n log n) para n intervalos: a ordenação custa O(n log n) e a varredura, O(n). Ela usa O(n) de espaço extra para os pares ordenados e o resultado.

Q: Por que ordenar os intervalos pelo início e não pelo fim?

Ordenado pelo início, um intervalo só pode se sobrepor ao grupo que você está formando, então uma comparação com o fim desse grupo resolve tudo. Ordenado pelo fim, um intervalo posterior pode começar antes de grupos que você já fechou: [5, 6] vem antes de [1, 10] , e uma varredura para a frente manteria incorretamente 5 como início.

Q: Você consegue mesclar intervalos sem usar espaço extra?

Sim, se você puder alterar a entrada. Ordene os intervalos no próprio lugar, depois escreva cada intervalo mesclado sobre o início do mesmo array e mantenha o índice do último que foi escrito. O tempo continua sendo O(n log n), e o único espaço extra é o usado pela ordenação da sua linguagem.

MédioIntervalos Ordenação

+10

Você recebe um conjunto de intervalos, cada um representando uma faixa de números inteiros de um início a um fim. Mescle cada grupo de intervalos sobrepostos em um único intervalo que cubra todo o grupo e retorne os intervalos mesclados ordenados pelo início. Intervalos que apenas se tocam, como [1, 4] e [4, 5], são considerados sobrepostos.

Os intervalos são fornecidos em dois arrays de mesmo tamanho: o intervalo i é [starts[i], ends[i]]. Você retorna um array bidimensional, uma lista de pares [start, end].

Função

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

startsinteger-array: o início de cada intervalo
endsinteger-array: o fim de cada intervalo, no mesmo índice que seu início
Retornainteger-2d-array: os intervalos mesclados como pares [start, end], ordenados por início

Restrições

1 ≤ starts.length == ends.length ≤ 10⁴
0 ≤ starts[i] ≤ ends[i] ≤ 10⁴
Os intervalos chegam em qualquer ordem.
Intervalos que apenas se tocam em uma extremidade são considerados sobrepostos.

Exemplos

Entrada: starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
Saída: [[1, 7], [12, 14]]
Explicação: Na ordem de início, [1, 4] se sobrepõe a [3, 6], que se sobrepõe a [5, 7], então os três se tornam [1, 7]. [12, 14] começa depois de 7 e permanece separado.

Para ir além

Os intervalos já chegam mesclados e ordenados pelo início, e você precisa adicionar um novo intervalo. Você consegue retornar a lista mesclada em O(n) tempo, sem ordenar novamente?

Solução

Mesclar pares em qualquer ordem exige passagens repetidas, porque cada mesclagem amplia um intervalo e permite que ele alcance intervalos que você já verificou. Em vez disso, ordene pelo início. Assim, um intervalo só pode se sobrepor ao grupo que você está construindo, e uma única passagem resolve o problema.

Mescle os pares sobrepostos até que nada mude

Correta, mas não termina nos maiores testes

Intuição

Os intervalos [a, b] e [c, d] se sobrepõem quando c ≤ b e a ≤ d, e [min(a, c), max(b, d)] cobre ambos. Cada união remove um intervalo, então o processo para e, quando uma passagem completa não encontra sobreposição, nenhum par de intervalos restantes compartilha um ponto. Uma passagem não é suficiente: um intervalo unido é mais amplo e agora pode alcançar um intervalo com o qual sua parte menor foi comparada anteriormente durante a passagem.

Uma passagem compara cerca de n²/2 pares, e talvez sejam necessárias até n passagens: O(n³). Uma única passagem por 10^4 intervalos já envolve 5 × 10^7 comparações.

Algoritmo

Copie starts e ends, e mantenha uma contagem n dos intervalos ativos.
Compare cada intervalo i com todos os intervalos posteriores j. Se eles se sobrepuserem, amplie i para abranger j, mova o último intervalo ativo para a posição j e diminua n em um.
Após uma mesclagem, verifique novamente a posição j, pois agora há um intervalo diferente nela.
Repita as passagens até que uma delas não faça nenhuma mesclagem.
Associe cada início ativo ao seu fim, ordene os pares pelo início e retorne-os.

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

Ordene pelo início e percorra uma vez

Intuição

Após ordenar pelo início, o próximo intervalo começa não antes de qualquer intervalo no último grupo, que termina em e. Se o início dele for menor ou igual a e, ele se sobrepõe ao grupo ou encosta nele, e se junta a ele; e se torna o maior dos dois finais. Se o início dele estiver depois de e, nenhum intervalo posterior poderá alcançar o grupo também, porque os intervalos seguintes começam mais à direita. O grupo está concluído, e o intervalo abre um novo.

A ordenação custa O(n log n), e a varredura visita cada intervalo uma vez. Os grupos são encerrados da esquerda para a direita, então o resultado sai ordenado pelo início.

Algoritmo

Associe cada início ao seu fim: o intervalo i é [starts[i], ends[i]].
Ordene os pares pelo início.
Percorra os pares ordenados. Se o resultado estiver vazio ou se o par começar depois do fim do último intervalo mesclado, adicione o par como um novo intervalo.
Caso contrário, defina o fim do último intervalo mesclado como o maior entre seu fim e o fim do par.
Retorne a lista mesclada.

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

Armadilhas e casos extremos

Comparar com < em vez de ≤. Intervalos que se tocam, como [1, 4] e [4, 5], devem ser mesclados.
Definir o fim como o fim do novo intervalo em vez de usar o maior dos dois. [1, 10] seguido por [2, 3] deve permanecer [1, 10].
Ordenar starts separadamente e depois ler ends nas novas posições, fazendo com que um início receba o fim de outro intervalo. Primeiro, forme os pares ou ordene os índices.
Comparar com o intervalo de entrada anterior em vez do último intervalo mesclado. Em [1, 10], [2, 3], [4, 5], o terceiro intervalo está dentro de [1, 10], embora não toque em [2, 3].
Em C, não definir *returnSize como o número de intervalos mesclados e o tamanho de cada coluna como 2.

Perguntas frequentes3

Qual é a complexidade de tempo de Merge Intervals?

A solução de ordenação e varredura é executada em tempo O(n log n) para n intervalos: a ordenação custa O(n log n) e a varredura, O(n). Ela usa O(n) de espaço extra para os pares ordenados e o resultado.

Por que ordenar os intervalos pelo início e não pelo fim?

Ordenado pelo início, um intervalo só pode se sobrepor ao grupo que você está formando, então uma comparação com o fim desse grupo resolve tudo. Ordenado pelo fim, um intervalo posterior pode começar antes de grupos que você já fechou: [5, 6] vem antes de [1, 10], e uma varredura para a frente manteria incorretamente 5 como início.

Você consegue mesclar intervalos sem usar espaço extra?

Sim, se você puder alterar a entrada. Ordene os intervalos no próprio lugar, depois escreva cada intervalo mesclado sobre o início do mesmo array e mantenha o índice do último que foi escrito. O tempo continua sendo O(n log n), e o único espaço extra é o usado pela ordenação da sua linguagem.

def mergeIntervals(starts, ends):
    # Escreva o código aqui

Teste #1

Teste #2

Argumentos

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

Saída Esperada

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