Cortar un intervalo de otros ordenados
La misión
Problema
Un conjunto de números se guarda como una lista ordenada de intervalos semiabiertos y disjuntos [a, b), cada uno de los cuales cubre todos los números desde a hasta b, sin incluir b. Dado un intervalo más, cut = [lo, hi), quita del conjunto todos los números que cubre y devuelve lo que queda, de nuevo como una lista ordenada de intervalos disjuntos.
Ejemplos
Input: spans = [[0, 2], [3, 4], [5, 7]], cut = [1, 6]
Output: [[0, 1], [6, 7]]
Por qué: el corte recorta el primer intervalo, se traga el segundo y recorta el tercero
Input: spans = [[0, 5]], cut = [2, 3]
Output: [[0, 2], [3, 5]]
Por qué: un corte dentro de un intervalo lo divide en dos
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é: caso límite: los intervalos que quedan por completo fuera del corte pasan intactos
Pistas
0 / 3
Mira cada intervalo por separado. Respecto al corte, solo puede estar por completo antes, por completo después o superpuesto con él.
Con intervalos semiabiertos, [a, b) no toca [lo, hi) exactamente cuando b <= lo o a >= hi. Esos intervalos se conservan enteros.
Un intervalo superpuesto puede dejar hasta dos pedazos: [a, lo) si empieza antes del corte, y [hi, b) si termina después. Emite los que existan de esos dos, en ese orden.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Restricciones
- the spans are sorted and disjoint
Solución
La lista ya está ordenada y sus intervalos son disjuntos, así que basta una pasada en orden y la salida sigue ordenada sin trabajo extra. Cada intervalo se compara con el corte una vez: si no se superponen, se copia, y si se superponen, solo sobreviven las partes que sobresalen por la izquierda y por la derecha. Un intervalo que el corte cubre por completo no produce ninguna parte y desaparece, y uno dentro del cual cae el corte produce las dos, que es la división. Usar intervalos semiabiertos mantiene limpia la aritmética, porque los pedazos que sobreviven terminan exactamente en lo y empiezan exactamente en hi, sin sumar ni restar uno. El tiempo es O(n) y la salida tiene como 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]]¿Lo que te frena es la idea y no el código? Insert Interval lo explica.