3
$\begingroup$

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?

$\endgroup$

closed as unclear what you're asking by Raphael Feb 25 '14 at 20:19

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ You might want to take a look at the algorithm used to reassemble fragmented IP datagrams. This has to determine when all the fragments have been received, which corresponds to covering the interval from 0 to size. $\endgroup$ – Barmar Feb 25 '14 at 20:14
  • 2
    $\begingroup$ This is a dump of a problem, not a question. If you have a specific question regarding the wording of the problem or about concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Feb 25 '14 at 20:19
  • $\begingroup$ Um, no, this is a question, hence the question mark. I have thought about this, but there is no reason to clutter the question with my work. I vote for it to be reopened, as it is an interesting problem. $\endgroup$ – user980123 Feb 25 '14 at 21:57
  • $\begingroup$ If you need a working solution for this problem in C++ - look at the Boost ICL library (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$ – HEKTO Feb 25 '14 at 22:10
  • $\begingroup$ I agree with Raphael. Related: We expect you to do some serious research on your own before asking, and to show us what you've tried. So, what research have you done? Hint: if you search on "interval" on this site and look through the first few search results, you'll immediately find some references to data structures for storing intervals, which then apply directly to your problem. This is a sign that you haven't done enough research before asking. In fact, it looks like the very first search result gives a solution to your problem: cs.stackexchange.com/q/14311/755 $\endgroup$ – D.W. Feb 26 '14 at 6:09
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Please try to not encourage undesirable posting behaviour. $\endgroup$ – Raphael Feb 25 '14 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$ – user980123 Feb 25 '14 at 21:49

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