# 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$

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$$.

• That doesn't uniquely define the $J$ intervals; there will typically be multiple ways to choose $J$ intervals that don't intersect with the $I$ intervals. – D.W. Oct 2 '19 at 6:20

(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).

1. Consider all intervals $$(I_n=[\![s_n,e_n]\!])_{0\leq n, and sort them by increasing start time $$s_n$$, breaking ties arbitrarily [time $$\mathcal{O}(p\cdot \log p)$$]
2. 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)$$.

• I didn't prove correction of the algorithm but it should be straightforward: steps 1 and 2 are fairly well-known (you should be able to find them by looking for 'merging overlapping intervals problem'). – eru-cs Oct 1 '19 at 21:57
• Definitely, the intervals were discrete, thank you for making the assumption. – Raito Oct 1 '19 at 22:39