Étant donné un ensemble d'intervalles $ (i_n) _n $ contenu dans $ [0, l] $, calculez l'intervalle le plus long en $ [0, l] $ qui a une intersection vide avec tous les $ (i_n) _n $

Question

Laisser être $ (I_n) _n $ un ensemble de $ p $ intervalles contenus chacun dans $ [0, l] $ pour $ L geq 1 $.

Je définis $ (J_n = [a_n, b_n]) _ n $ l'ensemble des intervalles qui ont une intersection vide avec $ I_n $ pour tous $ n in [[1, p]] $.

Je voudrais calculer efficacement $ max_n (b_n - a_n + 1) $.

Une idée de base que j'essaierais serait de:

(1) créer un arbre de segment pour $ (I_n) _n $ dans $ O (p ln p) $

(2) itérer $ [0, l] $ et compter la ligne la plus longue avant de rencontrer un intervalle couvert par $ (I_n) _n $ (Réinitialiser la "valeur maximale" à 0 jusqu'au prochain $ J_q $)

Qui pourrait me donner un algorithme dans $ O (l + p ln p) $, le problème est que $ L $ est vraiment grand dans mes cas, j'aimerais avoir un algorithme qui ne dépend pas $ L $.