Non-overlapping Intervals

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

A solução gulosa ordena pelo fim em O(n log n) e percorre os intervalos uma vez, então o total é O(n log n) , com espaço O(n) para a cópia ordenada. A versão de programação dinâmica é O(n²) , e testar cada conjunto a manter é O(2^n) .

MédioIntervalos Guloso

+10

O intervalo i vai de starts[i] até ends[i]. Retorne o menor número de intervalos que você precisa remover para que nenhum par 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.

Função

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

startsinteger-array: o início de cada intervalo
endsinteger-array: o final 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. Três não podem permanecer: [1,4] se sobrepõe a [2,3], e [3,6] se sobrepõe a [5,7].

Entrada: starts = [0, 0, 0]ends = [5, 5, 5]
Saída: 2
Explicação: Os três intervalos são [0,5], então quaisquer dois se sobrepõem. Um permanece e você remove 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 e nunca se sobrepõem, então você não remove nada e a resposta é 0.

Para ir além

Suponha que cada intervalo tenha um valor e você queira o maior valor total entre intervalos que não se sobrepõem. Manter o intervalo que termina primeiro ainda funciona?

Solução

Remover o menor número de intervalos possível é o mesmo que manter o maior número de intervalos que não se sobrepõem: a resposta é n menos essa quantidade. Uma regra gulosa encontra essa quantidade em O(n log n): entre os intervalos que ainda cabem, sempre mantenha aquele que termina primeiro.

Mantenha ou remova cada intervalo

Correta, mas não termina nos maiores testes

Intuição

Ordene os intervalos pelo início e decida, para cada um, se deve mantê-lo ou removê-lo. Você só pode mantê-lo se ele começar no fim do último intervalo mantido ou depois dele, para que os intervalos mantidos formem uma cadeia sem sobreposições. Tente as duas opções para cada intervalo e escolha a que resultar na maior contagem; a resposta é n menos essa contagem.

Cada intervalo pode dobrar o número de ramificações, 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 n pode chegar a 5000.

Algoritmo

Ordene os intervalos pelo início, mantendo cada início associado ao 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 é o último intervalo mantido (-1 se nenhum).
Após o fim, retorne 0. Caso contrário, use mostKept(i+1, last), que remove o intervalo i.
Se o intervalo i começar no fim de last ou depois dele, tente também 1 + mostKept(i+1, i) e mantenha o maior valor.
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 continua fazendo a mesma pergunta: qual é o comprimento da maior cadeia que termina neste intervalo? Responda uma vez para cada intervalo. Ordene pelo início e seja chain[i] o maior número de intervalos que você pode manter com o intervalo i por último.

Um intervalo que pode vir imediatamente antes de i termina no início de starts[i] ou antes, então começa mais cedo e aparece antes na ordem ordenada. Isso resulta em chain[i] = 1 + chain[j] para o melhor j desse tipo, ou 1 se nenhum se encaixar. No primeiro exemplo, os valores são 1, 1, 2 e 2, então você mantém 2 e remove 2.

O loop duplo faz n(n-1)/2 verificações: cerca de 12,5 milhões quando n = 5000.

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

Escolha o intervalo que termina primeiro. Existe uma solução ótima que o mantém: em qualquer conjunto máximo que você possa manter, troque o intervalo que começa primeiro por este. Ele termina não depois, então continua terminando antes ou no início do próximo intervalo mantido, e o conjunto mantém o mesmo tamanho, sem sobreposições. Todo intervalo que começa antes do fim dele se sobrepõe a ele e precisa ser removido; o que resta é o mesmo problema com os intervalos que começam no fim dele ou depois.

No primeiro exemplo, ordenados pelo fim, você mantém [2,3], remove [1,4], mantém [3,6] e remove [5,7]. Manter o intervalo mais curto, em vez disso, não funciona para [1,5], [4,7], [6,10]: [4,7] se sobrepõe aos outros dois e exige duas remoções, quando uma basta.

A ordenação custa O(n log n) e a varredura, O(n).

Algoritmo

Ordene os intervalos pelo fim, mantendo cada fim junto do seu início.
Mantenha o primeiro intervalo: defina lastEnd como o seu fim e removed como 0.
Para cada intervalo seguinte, se ele começar em lastEnd ou depois, mantenha-o e defina lastEnd como o seu fim.
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

Tratar intervalos que se tocam como sobrepostos. Com start > lastEnd em vez de start ≥ lastEnd, a sequência [1,2], [2,4], [4,6] resulta em 1 em vez de 0.
Ordenar pelo início e manter o intervalo anterior quando há sobreposição. Um intervalo amplo [0,100] então elimina [1,2], [3,4] e [5,6]: três remoções em vez de uma.
Comparar cada intervalo com seu vizinho na lista ordenada em vez de com o último intervalo mantido. No primeiro exemplo, [3,6] precisa ser comparado com o fim de [2,3], não com o de [1,4], que foi removido, ou o resultado será 3.
Ordenar starts e ends como duas listas separadas. Cada fim precisa permanecer junto ao seu próprio início.
Retornar quantos intervalos você mantém em vez de quantos remove.

Perguntas frequentes3

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

A solução gulosa ordena pelo fim em O(n log n) e percorre os intervalos uma vez, então o total é O(n log n), com espaço O(n) para a cópia ordenada. A versão de programação dinâmica é O(n²), e testar cada conjunto a manter é O(2^n).

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

Sim, com uma regra diferente para sobreposição. Percorra os intervalos pelo início e, quando o próximo se sobrepuser ao último intervalo mantido, conte uma remoção e mantenha aquele que terminar primeiro. Isso resulta na mesma contagem, no mesmo tempo O(n log n).

Intervalos não sobrepostos é o mesmo que o problema de seleção de atividades?

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

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

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada

Non-overlapping Intervals

Função

Restrições

Exemplos

Dicas

Solução

Mantenha ou remova cada intervalo

Cadeia mais longa com programação dinâmica

Guloso: mantenha o intervalo que termina primeiro

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos