Given a list of intervals $[s_1, e_1], [s_2, e_2], \ldots$, what's the most efficient way to determine if an interval $[a, b]$ can be covered by the intervals in the list?
1 Answer
I don't know if it's the most efficient algorithm, but here's my suggestion:
Your problem is somewhat similar to balancing parenthesis: you can put all $s_i$ and $e_i$ values on a list and sort it (Lets call this list $V$), but keep the type of each element ($s$ or $e$ element) attached to the value. Then use this list to integrate all the intervals with the following algorithm (uniting overlapping intervals to one interval):
create a list of intervals L, Create a stack St
for every element n in the sorted list V (from the smallest to the largest)
{
if n is an s element and St is empty
{
create a new interval I (a pair of numbers)
assign I.s = n
push some value to St
}
else if n is an s element and St isn't empty
{
push some value to St
}
else if n is an e element (stack can't be empty here)
{
pop a value from St
if St is empty
{
assign I.e = n
add interval I to the interval list L
}
}
}
return L
Now you have a list of integrated intervals, and checking if $[a,b]$ si covered by one of them is easy: for every interval $I$ in $L$, check if $a \geq I.s$ and $b \leq I.e$ (there are no overlapping intervals in $L$ now, they were integrated in the previous step).
Integrating the intervals to create $L$ takes $O(n)$ computation time and so is checking if $[a,b]$ is covered by one of the intervals in $L$, which makes the sorting $V$ the most expensive task here, $O(n\log{n})$.
Hope this helps, though there might be a linear time algorithm for performing this task...
-
1$\begingroup$ Please try to not encourage undesirable posting behaviour. $\endgroup$– Raphael ♦Feb 25, 2014 at 20:20
-
$\begingroup$ This is not homework. This is a question of mine and I'm curious to know the answer. I doubt any of my thoughts on solving this would be helpful, since I basically got nowhere. I submit for this question to be reopened. $\endgroup$ Feb 25, 2014 at 21:49
size
. $\endgroup$http://www.boost.org/doc/libs/1_55_0/libs/icl/doc/html/index.html
). However, their implementation is not easy to extract from their sources. $\endgroup$