É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 $
-
06-11-2019 - |
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 $.
Pas de solution correcte