Pular para o conteúdo

Cortar um intervalo da lista ordenada

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

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

Tempo-alvo
O(n)
Espaço-alvo
O(n)

Restrições

  • the spans are sorted and disjoint

Travou na ideia, e não no código? Insert Interval explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado