Saltar al contenido

Cortar un intervalo de otros ordenados

Fácil#interval-overlap#single-pass~15 min

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

Tiempo objetivo
O(n)
Espacio objetivo
O(n)

Restricciones

  • the spans are sorted and disjoint

¿Lo que te frena es la idea y no el código? Insert Interval lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio