patternMinor
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$
Viewed 0 times
thei_ncomputewithallintervalemptycontainedhasintervals
Problem
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$.
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$.
Solution
(From your notations, I assume the intervals are all discrete as otherwise some of the $J_n$ would not be closed. Furthermore, the length of the intervals would not be $b_n-a_n+1$ so I'm fairly certain that assumption is safe. If however that was not your intention, it should be straightforward enough to adapt the algorithm to the continuous case).
What we've done here is merge the intervals $(I_n)_n$ so as to rewrite $\bigcup I_n$ as an ordered stack of disjoint intervals. We shall call these intervals $(\tilde{I}_n=[\![\tilde{s}_n,\tilde{b}_n]\!])_n$
Now iterate linearly through the stack to find the largest interval separating two successive intervals on the stack (without forgetting the two intervals $[\![0,\tilde{s}_0[\![$ and $]\!]\tilde{s}_{-1},L]\!]$) [time $\mathcal{O}(p)$]
Overall the runtime is $\mathcal{O}(p\cdot \log p)$.
- Consider all intervals $(I_n=[\![s_n,e_n]\!])_{0\leq n
- Build a stack containing only the first interval (i.e. the one with the smallest start). For each subsequent interval: if [the interval doesn't overlap with the head of the stack] then [push it] else [merge it with the head of the stack] [time $\mathcal{O}(p)$]
What we've done here is merge the intervals $(I_n)_n$ so as to rewrite $\bigcup I_n$ as an ordered stack of disjoint intervals. We shall call these intervals $(\tilde{I}_n=[\![\tilde{s}_n,\tilde{b}_n]\!])_n$
Now iterate linearly through the stack to find the largest interval separating two successive intervals on the stack (without forgetting the two intervals $[\![0,\tilde{s}_0[\![$ and $]\!]\tilde{s}_{-1},L]\!]$) [time $\mathcal{O}(p)$]
Overall the runtime is $\mathcal{O}(p\cdot \log p)$.
Context
StackExchange Computer Science Q#115330, answer score: 5
Revisions (0)
No revisions yet.