The intervals are represented as two numbers, e.g. $(4.3, 5.6)$. The intervals are unique.

If for $(x,y)$ and $(u,v)$, $x≤u$ and $v≤y$, $(u,v)$ is nested in $(x,y)$

How do I find out which intervals are nested in others efficiently?

The hint is to use two induction hypotheses: one to assume you can solve the problem for $n-1$ intervals, another that you can find the largest right endpoint for the $n-1$ intervals.

How do I use this information to do the inductive step in constant time?

  • $\begingroup$ Perhaps you mean $(u, v)$ is nested in $(x, y)$ if $x \le u$ and $y \ge v$. $\endgroup$
    – Paresh
    Commented Dec 1, 2012 at 19:26
  • $\begingroup$ I seem to have reversed the two. Thanks. $\endgroup$ Commented Dec 2, 2012 at 6:13
  • $\begingroup$ One question: what is exactly the problem here? It seems to me that the whole statement would be something like: Given a set of intervals $L$ and a new interval $I$ to find those from the original list that contain the given interval in $O(1)$, is it? I do sincerely doubt there is a constant-time algorithm to perform this task and maybe the most efficient algorithm can only do it in logarithmic time ... $\endgroup$ Commented Dec 2, 2012 at 11:15
  • $\begingroup$ Sorry, will rewrite the question tonight when I get more time. I suspect I phrased it badly. $\endgroup$ Commented Dec 2, 2012 at 14:36

2 Answers 2


A solution must look like this: we have list of intervals and we must tell for a new interval which of the intervals contain it and which of the list are contained in the new interval.

A logical start will be that the list of intervals are sorted in some data structure and we need to add the new interval in its proper place. In the general case an insertion into some sorted list can be done in time complexity $O(log n)$, when using self-balancing binary search tree for example.

I am not sure if for the general case it is possible to reach $O(1)$ time. However to beat the logarithmic time you may need to add some limitations. It is clear that for the insertion we must not use comparison. One limited solution can be done by using modified counting sort. This however will work only if we know that the interval's points are limited to positive integer values in some interval(you can enhance the solution to work for sets that are countable and finite, if you assume that you don't have infinite memory).

Example: If we have $n=4$ the following list $(1, 8), (3, 6), (2, 3)$ and you want to add a new interval $(4, 5)$

intervals We can order them in array with size $n$ X largest right endpoint: in the first row we place interval's IDs in the cell with the number of the start/end point. If this cell already has an ID we are using the cell in the bottom row. We can keep a counter to the fullness level of each column.

array before insertion

We can add the same way the new interval in $O(1)$ time and have the intervals ordered by their nesting again in constant time.

enter image description here

Here is some pseudo code of the operaion in the n-th step:

Input:new_interval = (x,y)
    array[x][x_column_counter] = new_interval_id
    array[y][y_column_counter] = new_interval_id
  • $\begingroup$ Will look closer at solution later, but thanks. $\endgroup$ Commented Dec 2, 2012 at 17:56
  • $\begingroup$ Adding the interval to the table is ok, but how do you "order the nesting" in constant time? From the second table above, how do find out which intervals completely cover the newly added interval [4, 5]? $\endgroup$
    – Paresh
    Commented Dec 2, 2012 at 18:20
  • $\begingroup$ The insertion is done in constant time and the "output" of the operation is the array itself. The covers of each interval can be found by iterating through the array left from the start and right from the end and matching the interval ids for example. $\endgroup$
    – Anton
    Commented Dec 2, 2012 at 19:12
  • $\begingroup$ umm ... won't that be $O(n)$ instead of $O(1)$? Am I missing something? $\endgroup$
    – Paresh
    Commented Dec 2, 2012 at 19:20
  • $\begingroup$ The question is how to do the inductive step in constant time? So the inductive step is : if we have done this for $n-1$ intervals how can we do it for the $n$th interval. I have added some pseudo code in the answer. $\endgroup$
    – Anton
    Commented Dec 2, 2012 at 20:12

This problem is as hard as comparison sorting, given n input number sort them.

You can make interval set from input number set $S$ (w.l.o.g suppose input numbers are in $Z^+$) as follow:

$ \Gamma = \{(a,b) \mid a\in S \wedge b=\max_{t\in S} \{2\cdot t - a + 1 \} \}$

Above transformation can be done in $O(n)$.

But if you find a nesting relation in this interval set in $o(n \log n)$, you can sort input array in $o(n \log n)$, But comparison sorting barrier is $\Omega(n \log n)$, So the algorithm which finds interval nesting cannot be better than $\Omega(n \log n)$ with respect to comparision sorting barrier, But also $O(n \log n)$ algorithm is trivial.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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