Mam serię przedziałów czasowych (t_start, t_end), które nie mogą się nakładać, tj .: t_end (i)> t_start (i + 1). Chcę wykonać następujące operacje:

1) Dodaj nowe (Union) interwały [{(1,4), (8,10)} U (3,7) = {(1,7), (8,10)}]
2) Odstępy czasowe [(1,7) - (3,5) = {(1,3), (5,7)}
3) Sprawdzanie, czy punkt lub przedział nakładają się z interwałem w mojej serii (przecięcie)
4) Znalezienie pierwszego „braku interwału” o minimalnej długości po pewnym punkcie [{(1,4), (7,8)}: istnieje „brak interwału” o długości 3 między 4 a 7].

Chcę poznać dobre sposoby implementacji tego rozwiązania, z niską złożonością (log n dla wszystkich operacji by to zrobił).

Podobne pytanie:Sprawdź strukturę danych dla szybkiego interwału czasowego