Cortar um intervalo da lista ordenada
A missão
Problema
Um conjunto de números é guardado como uma lista ordenada de intervalos semiabertos e disjuntos [a, b), cada um cobrindo todos os números de a até b, sem incluir b. Dado mais um intervalo cut = [lo, hi), remova do conjunto todos os números que ele cobre e retorne o que sobrar, de novo como uma lista ordenada de intervalos disjuntos.
Exemplos
Input: spans = [[0, 2], [3, 4], [5, 7]], cut = [1, 6]
Output: [[0, 1], [6, 7]]
Por quê: o corte apara o primeiro intervalo, engole o segundo e apara o terceiro
Input: spans = [[0, 5]], cut = [2, 3]
Output: [[0, 2], [3, 5]]
Por quê: um corte dentro de um intervalo o divide em dois
Input: spans = [[-5, -4], [-3, -2], [1, 2], [3, 5], [8, 9]], cut = [-1, 4]
Output: [[-5, -4], [-3, -2], [4, 5], [8, 9]]
Por quê: edge case: intervalos inteiramente fora do corte passam intactos
Dicas
0 / 3
Olhe para cada intervalo isoladamente. Em relação ao corte, ele só pode estar inteiramente antes dele, inteiramente depois dele ou se sobrepondo a ele.
Com intervalos semiabertos, [a, b) fica fora de [lo, hi) exatamente quando b <= lo ou a >= hi. Esses intervalos são mantidos inteiros.
Um intervalo que se sobrepõe ao corte pode deixar até dois pedaços: [a, lo) se ele começa antes do corte, e [hi, b) se ele termina depois. Emita os que existirem, nessa ordem.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Restrições
- the spans are sorted and disjoint
Solução
A lista já está ordenada e é disjunta, então uma passada em ordem basta, e a saída continua ordenada sem nenhum trabalho extra. Cada intervalo é comparado com o corte uma vez: se não houver sobreposição, ele é copiado; se houver, só sobrevivem as partes que ficam para fora à esquerda e à direita. Um intervalo que o corte cobre por completo não produz nenhuma parte e desaparece, e um intervalo dentro do qual o corte cai produz as duas, que é a divisão. Intervalos semiabertos mantêm a aritmética limpa, porque os pedaços que sobram terminam exatamente em lo e começam exatamente em hi, sem nenhum mais um ou menos um. O tempo é O(n), e a saída tem no máximo n + 1 intervalos.
def cut_span(spans, cut):
lo, hi = cut
out = []
for a, b in spans:
if b <= lo or a >= hi: # no overlap: keep the whole span
out.append([a, b])
continue
if a < lo:
out.append([a, lo]) # the part left of the cut survives
if b > hi:
out.append([hi, b]) # the part right of the cut survives
return out
print(cut_span([[0, 2], [3, 4], [5, 7]], [1, 6])) # -> [[0, 1], [6, 7]]
print(cut_span([[0, 5]], [2, 3])) # -> [[0, 2], [3, 5]]
print(cut_span([[-5, -4], [-3, -2], [1, 2], [3, 5], [8, 9]], [-1, 4])) # -> [[-5, -4], [-3, -2], [4, 5], [8, 9]]Travou na ideia, e não no código? Insert Interval explica isso.