İçeriğe geç

Sıralı aralıklardan bir aralık kes

Kolay#interval-overlap#single-pass~15 dk

Görev tanımı

Problem

Bir sayı kümesi (set), her biri a'dan b'ye kadar, b hariç, her sayıyı kapsayan yarı açık [a, b) aralıklarından oluşan sıralı ve ayrık bir liste olarak saklanıyor. Bir aralık daha, cut = [lo, hi), verildiğinde, onun kapsadığı her sayıyı kümeden sil ve kalanı yine sıralı ve ayrık aralıklardan oluşan bir liste olarak döndür.

Örnekler

Input:  spans = [[0, 2], [3, 4], [5, 7]], cut = [1, 6]
Output: [[0, 1], [6, 7]]
Neden: kesim ilk aralığı kırpar, ikincisini yutar, üçüncüsünü kırpar
Input:  spans = [[0, 5]], cut = [2, 3]
Output: [[0, 2], [3, 5]]
Neden: tek bir aralığın içindeki kesim onu ikiye böler
Input:  spans = [[-5, -4], [-3, -2], [1, 2], [3, 5], [8, 9]], cut = [-1, 4]
Output: [[-5, -4], [-3, -2], [4, 5], [8, 9]]
Neden: edge case: tamamen kesimin dışındaki aralıklar dokunulmadan geçer

İpuçları

0 / 3

Hedef zaman
O(n)
Hedef alan
O(n)

Kısıtlar

  • the spans are sorted and disjoint

Kodda değil de fikirde mi takıldın? Insert Interval bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case