Algorithm to determine if an interval is covered by a list of intervals? [closed]

Question

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?

Answer 1

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