Non-overlapping Intervals

Q: Qual é a complexidade de tempo de intervalos não sobrepostos?

A solução gulosa ordena os intervalos pelo fim em O(n log n) e depois percorre todos uma vez em O(n) , então o total é O(n log n) . A cópia ordenada dos intervalos usa espaço O(n) . A versão de programação dinâmica é O(n²) , e testar todos os conjuntos possíveis para manter é O(2^n) .

MédioIntervalos Guloso

+10

Você recebe uma lista de intervalos em dois arrays: o intervalo i vai de starts[i] a ends[i]. Remova o menor número possível de intervalos para que nenhum dos intervalos restantes se sobreponha. Dois intervalos que apenas se tocam, quando um termina exatamente no ponto em que o outro começa, não se sobrepõem.

Escreva uma função chamada eraseOverlapIntervals que retorne o menor número de intervalos que você precisa remover.

Função

eraseOverlapIntervals(starts: integer-array, ends: integer-array) → integer

startsinteger-array: o início de cada intervalo
endsinteger-array: o fim de cada intervalo, no mesmo índice que seu início
Retornainteger: o menor número de intervalos a remover para que os restantes não se sobreponham

Restrições

1 ≤ starts.length == ends.length ≤ 5000
-5 × 10⁴ ≤ starts[i] < ends[i] ≤ 5 × 10⁴
Os intervalos não estão ordenados. Dois intervalos podem ser idênticos.

Exemplos

Entrada: starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
Saída: 2
Explicação: Na ordem de início, os intervalos são [1,4], [2,3], [3,6] e [5,7]. Mantenha [2,3] e [3,6], que apenas se tocam, e remova os outros 2. Não é possível manter três: [1,4] se sobrepõe a [2,3] e [3,6] se sobrepõe a [5,7], e quaisquer três dos quatro contêm um desses pares.

Entrada: starts = [0, 0, 0]ends = [5, 5, 5]
Saída: 2
Explicação: Os três intervalos são todos [0,5], então quaisquer dois deles se sobrepõem. Apenas um pode permanecer, e você remove os outros 2.

Entrada: starts = [4, 1, 2]ends = [6, 2, 4]
Saída: 0
Explicação: [1,2], [2,4] e [4,6] se encontram pelo fim e pelo início, sem nunca se sobrepor, então você não remove nada e a resposta é 0.

+17 testes ocultos ao enviar

Para ir além

Suponha que cada intervalo também tenha um valor e que você queira obter o maior valor total entre os intervalos que não se sobrepõem. Manter o intervalo que termina primeiro ainda funciona? O que você usaria em vez disso?

Solução

Remover o menor número de intervalos é o mesmo que manter o maior número de intervalos que não se sobrepõem, então a resposta é n menos esse maior conjunto. Tentar todos os conjuntos possíveis é exponencial, e a programação dinâmica sobre cadeias de intervalos reduz isso para O(n²). Uma regra gulosa resolve o problema em O(n log n): entre os intervalos que ainda cabem, mantenha sempre aquele que termina primeiro.

Manter ou remover cada intervalo

Correta, mas não termina nos maiores testes

Intuição

Inverta a pergunta. Remover o menor número de intervalos significa manter o maior número de intervalos que não se sobrepõem, e a resposta é n menos esse número. Portanto, procure o maior conjunto que você pode manter.

Ordene os intervalos pelo início e decida, para cada um, nessa ordem, se deve removê-lo ou mantê-lo. Você só pode mantê-lo se ele começar no final ou depois do último intervalo que manteve. Essa única verificação é suficiente: os intervalos mantidos formarão então uma cadeia em que cada um começa no final ou depois do anterior, portanto, nenhum par se sobrepõe. Tente as duas opções em cada intervalo e escolha o melhor resultado.

No primeiro exemplo, os intervalos ordenados são [1,4], [2,3], [3,6], [5,7]. Manter [1,4] bloqueia [2,3] e [3,6], que começam antes de 4, e deixa espaço para [5,7]: 2 mantidos. Remover [1,4] e manter [2,3] e depois [3,6] também mantém 2. Nenhum ramo chega a 3, então você remove 4-2 = 2.

Cada intervalo pode dobrar o número de ramos, então n intervalos levam a até 2^n caminhos. Trinta intervalos que não se sobrepõem já significam mais de um bilhão de chamadas, e os testes chegam a 5000 intervalos. A recursão também chega a n níveis de profundidade: 5000 chamadas nos maiores testes, ultrapassando o limite padrão de Python, que é 1.000.

Algoritmo

Ordene os intervalos pelo início, mantendo cada início junto com seu próprio fim.
Defina mostKept(i, last): o maior número de intervalos que você pode manter a partir da posição i, quando last é a posição do intervalo mantido mais recente (-1 para nenhum).
Depois do fim da lista, retorne 0. Caso contrário, comece com mostKept(i+1, last), o resultado de remover o intervalo i.
Se o intervalo i começar no fim ou depois do fim do intervalo last, tente também 1 + mostKept(i+1, i) e mantenha o maior resultado.
Retorne n menos mostKept(0, -1).

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)

    def most_kept(i, last):
        # The most intervals you can keep among i..n-1, when interval last
        # is the latest one kept so far (-1: nothing kept yet).
        if i == n:
            return 0
        best = most_kept(i + 1, last)  # remove interval i
        if last == -1 or intervals[i][0] >= intervals[last][1]:
            best = max(best, 1 + most_kept(i + 1, i))  # keep interval i
        return best

    return n - most_kept(0, -1)

Cadeia mais longa com programação dinâmica

Correta, mas não termina nos maiores testes

Intuição

A busca acima responde à mesma pergunta repetidamente: qual é a maior cadeia que termina neste intervalo? Armazene essa resposta uma vez por intervalo. Ordene pelo início e defina chain[i] como o maior número de intervalos que você pode manter quando o intervalo i é o último mantido.

O intervalo mantido imediatamente antes de i precisa terminar em starts[i] ou antes. Todo intervalo assim vem antes na ordem ordenada: ele começa antes de terminar, então começa antes de starts[i]. Isso dá chain[i] = 1 + chain[j] para o melhor j anterior com ends[j] ≤ starts[i], ou 1 quando nenhum intervalo se encaixa. O maior valor em chain é o máximo que você pode manter.

No primeiro exemplo, ordenados como [1,4], [2,3], [3,6], [5,7], os valores são 1, 1, 2 e 2: [3,6] pode vir depois de [2,3], e [5,7] pode vir depois de [1,4] ou [2,3]. A maior cadeia tem tamanho 2, então você remove 4-2 = 2.

Cada intervalo verifica todos os intervalos anteriores, o que resulta em n(n-1)/2 verificações. Com n = 5000, são cerca de 12,5 milhões de verificações: é aceitável em uma linguagem compilada, lento demais nas linguagens mais lentas para os maiores testes e muito inferior à abordagem gulosa abaixo.

Algoritmo

Ordene os intervalos pelo início, mantendo cada início associado ao seu próprio fim.
Defina chain[i] = 1 para cada intervalo.
Para cada i e cada j < i com ends[j] ≤ starts[i], defina chain[i] como chain[j]+1 quando esse valor for maior.
Retorne n menos o maior valor em chain.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)
    # chain[i]: the most intervals you can keep when interval i is the last one kept
    chain = [1] * n
    for i in range(n):
        for j in range(i):
            if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
                chain[i] = chain[j] + 1
    return n - max(chain)

Guloso: mantenha o intervalo que termina primeiro

Intuição

Observe o intervalo com o menor fim. Uma resposta ótima sempre o mantém. Pegue qualquer conjunto máximo de intervalos que você possa manter e troque o intervalo mais cedo desse conjunto por este. O novo intervalo termina não depois do intervalo que substituiu, então ainda termina no início ou antes do início do próximo intervalo mantido. O conjunto continua sem sobreposições e mantém o mesmo tamanho, portanto manter o intervalo com o fim mais cedo nunca custa nada.

Depois de mantê-lo, todo intervalo que começa antes do fim dele se sobrepõe a ele e precisa ser removido. O que resta é a mesma questão para os intervalos que começam no fim dele ou depois, então aplique a mesma regra novamente. Na prática: ordene pelo fim, percorra a lista e lembre-se de lastEnd, o fim do último intervalo mantido. Mantenha um intervalo que comece no valor de lastEnd ou depois; conte qualquer outro intervalo como removido.

O primeiro exemplo, ordenado pelo fim, é [2,3], [1,4], [3,6], [5,7]. Mantenha [2,3], então lastEnd = 3. [1,4] começa em 1, antes de 3: remova-o. [3,6] começa em 3, não antes de 3: mantenha-o, lastEnd = 6. [5,7] começa em 5, antes de 6: remova-o. Dois removidos.

Outros critérios parecem tentadores, mas não funcionam. Ordenar pelo início mantém [0,100] quando ele cobre [1,2], [3,4] e [5,6], e remove três intervalos em vez de um. Manter o intervalo mais curto falha com [1,5], [4,7], [6,10]: o curto [4,7] se sobrepõe aos outros dois, então mantê-lo custa duas remoções, quando uma basta. O fim é o critério que deixa mais espaço para tudo o que vem depois.

A ordenação custa O(n log n) e a varredura, O(n). A cópia ordenada dos intervalos ocupa O(n) de espaço.

Algoritmo

Ordene os intervalos pelo fim, mantendo cada fim associado ao seu próprio início.
Mantenha o primeiro intervalo: defina lastEnd como o fim dele e removed como 0.
Para cada intervalo seguinte, se ele começar em lastEnd ou depois, mantenha-o e defina lastEnd como o fim dele.
Caso contrário, adicione 1 a removed.
Retorne removed.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(ends, starts))  # by end time
    removed = 0
    last_end = intervals[0][0]  # the interval that ends first is always kept
    for end, start in intervals[1:]:
        if start >= last_end:
            last_end = end  # it fits after the last kept interval: keep it
        else:
            removed += 1  # it overlaps the last kept interval: remove it
    return removed

Armadilhas e casos extremos

A maioria das respostas erradas vem da chave de ordenação ou da comparação em um ponto de contato.

Tratar intervalos que se tocam como sobrepostos. Usando start > lastEnd em vez de start ≥ lastEnd, a sequência [1,2], [2,4], [4,6] perde [2,4], que começa exatamente onde [1,2] termina, e a resposta dá 1 em vez de 0.
Ordenar pelo início e sempre manter o intervalo anterior em caso de sobreposição. Um intervalo amplo [0,100] acaba descartando [1,2], [3,4] e [5,6]. Se você ordenar pelo início, mantenha aquele dos dois intervalos sobrepostos que terminar primeiro.
Comparar cada intervalo com seu vizinho na lista ordenada em vez de compará-lo com o último intervalo mantido. Depois de remover [1,4], o próximo intervalo deve ser comparado com o fim de [2,3], não com 4.
Ordenar starts e ends como duas listas separadas. Cada fim precisa permanecer junto do seu próprio início; caso contrário, você compara um início com o fim de outro intervalo.
Retornar quantos intervalos você mantém. A questão pede o número de intervalos removidos, que é n menos esse valor.

Perguntas frequentes4

Qual é a complexidade de tempo de intervalos não sobrepostos?

A solução gulosa ordena os intervalos pelo fim em O(n log n) e depois percorre todos uma vez em O(n), então o total é O(n log n). A cópia ordenada dos intervalos usa espaço O(n). A versão de programação dinâmica é O(n²), e testar todos os conjuntos possíveis para manter é O(2^n).

Por que ordenar pelo horário de término resulta no menor número de remoções?

O intervalo que termina primeiro pode substituir o primeiro intervalo de qualquer resposta ótima sem criar sobreposição, pois termina no mesmo momento ou antes. Portanto, existe uma resposta ótima que o mantém e, depois de remover tudo o que se sobrepõe a ele, o restante é o mesmo problema em um conjunto menor. Repetir o argumento mostra que cada escolha gulosa é segura.

Você pode ordenar pelo horário de início?

Sim, com uma regra diferente para sobreposição. Percorra os intervalos pela posição inicial e, quando o próximo se sobrepuser ao último intervalo mantido, conte uma remoção e mantenha aquele que terminar primeiro. Ela remove o mesmo número de intervalos que a ordenação pelo término e é executada no mesmo tempo O(n log n).

Intervalos sem sobreposição são o mesmo que o problema de seleção de atividades?

É o outro lado da questão. A seleção de atividades busca o maior número de intervalos que não se sobrepõem; este problema pede o menor número a remover, que é n menos esse número. A mesma regra gulosa, manter a atividade que termina primeiro, resolve ambos.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

Non-overlapping Intervals

Função

Restrições

Exemplos

Dicas

Solução

Manter ou remover cada intervalo

Cadeia mais longa com programação dinâmica

Guloso: mantenha o intervalo que termina primeiro

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos