Dato un set di intervalli $ (i_n) _n $ contenuto in $ [0, l] $, calcola l'intervallo più lungo in $ [0, l] $ che ha un incrocio vuoto con tutti $ (i_n) _n $

Question

Lascia che sia $ (I_n) _n $ un insieme di $ p $ intervalli ciascuno contenuto in $ [0, l] $ per $ L geq 1 $.

Definisco $ (J_n = [a_n, b_n]) _ n $ l'insieme di intervalli che hanno un incrocio vuoto con $ I_n $ per tutti $ n in [[1, p]] $.

Vorrei calcolare in modo efficiente $ max_n (b_n - a_n + 1) $.

Un'idea di base che proverei sarebbe quella di:

(1) Crea un albero di segmenti per $ (I_n) _n $ in $ O (p ln p) $

(2) Iterazione $ [0, l] $ e conta la linea più lunga prima di incontrare un intervallo coperto da $ (I_n) _n $ (reimpostare il "valore massimo" a 0 fino a un certo $ J_q $)

Che potrebbe darmi un algoritmo in $ O (l + p ln p) $, il problema è che $ L $ è davvero grande nei miei casi, mi piacerebbe avere un algoritmo da cui non dipende $ L $.