3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Oct 2 at 6:20
5
$\begingroup$

(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<p}$, 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)$.

$\endgroup$
  • $\begingroup$ 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'). $\endgroup$ – eru-cs Oct 1 at 21:57
  • $\begingroup$ Definitely, the intervals were discrete, thank you for making the assumption. $\endgroup$ – Raito Oct 1 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.