Given a set of intervals $(I_n)_n$ contained in $[0, L]$, compute the longest interval in $[0, L]$ which has empty intersection with all $(I_n)_n$
-
06-11-2019 - |
Pergunta
Let be $(I_n)_n$ a set of $p$ intervals each contained in $[0, L]$ for $L \geq 1$.
I define $(J_n = [a_n, b_n])_n$ the set of intervals which have empty intersection with $I_n$ for all $n \in [[1, p]]$.
I'd like to efficiently compute $\max_n (b_n - a_n + 1)$.
A basic idea I'd try would be to:
(1) Create a segment tree for $(I_n)_n$ in $O(p \ln p)$
(2) Iterate over $[0, L]$ and count the longest line before encountering an interval covered by $(I_n)_n$ (resetting the "max value" to 0 until the next of a certain $J_q$)
Which could give me an algorithm in $O(L + p \ln p)$, the problem is that $L$ is really big in my instances, I'd like to have an algorithm which does not depend on $L$.
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange