Assume we have a (multi)set of nontrivial intervals $\mathcal{I} = \{I_1,...,I_n\}$ and for any two $I_i, I_j \in \mathcal{I}$, we have that $I_i \cap I_j$ is trivial (that is: contains at most one point), or one of them contains the other. Just to clarify, an example would be $\mathcal{I} = \{[0,10], [2,6],[6,8], [2,4],[2,3],[5,6],[6,7]\}$. For the sake of simplicity, assume there is a longest interval that contains all other intervals, call that the root.

We can arrange such (multi)sets as a tree where $I_i$ is a descendant of $I_j$ iff $I_i \subseteq I_j$ (if an interval has multiplicity $> 1$, then its multiple occurrences can form a path in the tree). What I want to do is find such a tree. It's clearly possible in $\mathcal{O}(n^2)$ time: sort the intervals by length in descending order and process them in that order. Whenever we insert the next interval $I_i$ into the tree, find the shortest interval already in the tree $I_j$ such that $I_i \subseteq I_j$; such an $I_j$ must exist since the root contains all other intervals.

I would like to do this in $\mathcal{O}(n \log n)$ time and it seems to me that should be possible. Rough ideas include using interval trees and trying to construct the tree from the bottom up starting from its leaves, or figuring out how to annotate search trees to do something like this for me, but nothing successful so far.

up vote 4 down vote accepted

You can solve it in $O(n \lg n)$ time using a divide-and-conquer algorithm.

Explaining the main idea: a cleaner variant

To help me explain the main idea, I'm going to change the problem slightly. I'll assume we're given a set of intervals, with no interval appearing more than once in the set, and where for any pair of overlapping intervals $I,I'$, one of them contains the other (i.e., either $I \subset I'$ or $I' \subset I$). The goal is to output a forest (a collection of trees).

This variant of the problem is slightly more general, in that we're not assuming we have a single root interval that all others are contained in. It's also slightly more specific in that I'm assuming we don't have the case of a trivial overlap containing a single point.

I'll show later in my answer how to remove these extra assumptions, but for now, let's go with this variant of the problem, as it makes explaining the main ideas easier.

Main idea: an algorithm for the cleaner variant

We'll use divide-and-conquer. Let $x$ denote the median of the $2n$ endpoints of the intervals. This can be computed in $O(n)$ time.

Use $x$ to partition the intervals into three collections:

  • The intervals that are wholly to the left of $x$ (i.e., their right endpoint is strictly less than $x$).

  • The intervals that are wholly to the right of $x$ (i.e., their left endpoint is strictly greater than $x$).

  • The intervals that contain $x$.

We'll first compute three forests, one forest for each of these three collections. Call these forests $\mathcal{L}$ (the forest of the intervals on the left), $\mathcal{R}$ (for the intervals on the right), and $\mathcal{M}$ (for the intervals that contain $x$). You can compute $\mathcal{L}$ and $\mathcal{R}$ by invoking the algorithm recursively. You can compute $\mathcal{M}$ directly by sorting the intervals that contain $x$ by decreasing width and building a path of the intervals by descending size (each node in $\mathcal{M}$ has exactly one child; it is the next-smallest interval).

Now we need to join together the forests $\mathcal{L},\mathcal{R},\mathcal{M}$. Since $\mathcal{M}$ is a path, given an interval $I$, you can find the smallest interval $I' \in \mathcal{M}$ such that $I \subset I'$ by using binary search. Therefore, to join the forests, take the roots of $\mathcal{L}$ and $\mathcal{R}$ and use binary search in $\mathcal{M}$ to find the smallest interval containing it, and add a corresponding child relationship. This is all you need to do to join them into a single forest, as there can be no other child relationships between $\mathcal{L},\mathcal{R},\mathcal{M}$. Output the resulting forest.

What's the running time of this procedure? Well, it takes $O(n)$ time to partition the intervals into these three collections. You can compute $\mathcal{M}$ in $O(n)$ time (if you've done a single up-front precomputation to sort the intervals by decreasing width). It will take at most $O(n \lg n)$ time to join $\mathcal{L}, \mathcal{R}, \mathcal{M}$ into a single forest, since each binary search operation can be done in $O(\lg n)$ time. With a little more cleverness, you can speed up the merging to run in $O(n)$ time (pre-sort the intervals by their left endpoint once, and by the right endpoint; now you can join $\mathcal{L}$ and $\mathcal{M}$ by doing a merge on the sorted list of intervals of $\mathcal{L}$ and the sorted list of intervals of $\mathcal{M}$, both sorted by their left endpoint; join $\mathcal{R}$ and $\mathcal{M}$ similarly). Therefore, the running time is $O(n)$ plus the time for the two recursive calls. Finally, note that each recursive call is on at most $n/2$ intervals, due to the way we chose $x$ (there can be at most $n/2$ intervals wholly to the left of $x$, as each such interval contributes 2 endpoints to the $2n$ endpoints, and at most $n/2$ intervals wholly to the right of $x$).

Therefore, we get the recurrence relation

$$T(n) = 2 T(n/2) + O(n),$$

whose solution is $T(n) = O(n \lg n)$.

Solving your original problem

Your original problem allows a pair of intervals to overlap in a single point, without either one containing the other. This doesn't fundamentally change the problem. You need to generalize the method for computing $\mathcal{M}$ slightly, as it is no longer guaranteed to be a simple path, but this is not hard to do. Also, now $\mathcal{M}$ might have two leaves. If so, for each root of $\mathcal{L},\mathcal{R}$, you need to compare it to both leaves to see whether it is contained in either one. This doesn't change the overall running time.

Also, your original problem allows some intervals to appear in the input twice. This is easy to accommodate: remove duplicates, count how many times each interval appears in the input, run the algorithm above, and then adjust the tree to account for multiplicities (e.g., by duplicating nodes, or however you would like them to appear in the final output).

  • Thanks for your very elaborate answer! I'll check back tomorrow, too late tonight for me to think it through properly. The partitioning in the beginning already reminds me of interval trees, which seemed related to me. – G. Bach Feb 6 '15 at 23:25
  • Very interesting idea! Could you explain why $\mathcal{L}$ and $\mathcal{R}$ can only be children of the leaf of $\mathcal{M}$, or otherwise they must be unrelated to it? I can't quite follow that. – G. Bach Feb 7 '15 at 22:48
  • With respect to the generalization to forests: I considered whether that adds anything to the problem when I posted the question, and since adding an interval that is a strict superset of the union of all intervals (which we can do in $\mathcal{O}(n)$ time) that we later delete again is a simple reduction to the case where the forest is a tree, I thought it did not. However, seeing this answer, I think that may not be the smartest way out, since that diverted me from thinking about the problem in the terms you did! – G. Bach Feb 7 '15 at 22:52
  • @G.Bach, you are right. That statement wasn't right. I've updated my answer to explain how to join $\mathcal{L}$, $\mathcal{R}$, and $\mathcal{M}$ properly (it requires a binary search for each root of $\mathcal{L}$ or $\mathcal{R}$, to find which element of $\mathcal{M}$ that root should become a child of). – D.W. Feb 8 '15 at 1:48

What about another sorting order, which seems to be compatible with pre-order in your proposed trees?

Define $I \le I'$ with $I=[a,b]$ and $I'=[c,d]$ iff $I$ is before $I'$, i.e., $b\le c$, of $I$ contains $I'$, i.e., $a\le c$ and $d\le b$.

  • Interesting, I'll remember that approach to think about rooted trees! I'll leave the question open for just a little longer to see if someone else has a different idea. – G. Bach Feb 6 '15 at 14:03
  • As far as I can see, this doesn't answer the question. Should it be a comment? (Or if it is somehow answering the question, I think the idea needs more elaboration, as I cannot see how this answers the question that was asked.) – D.W. Feb 6 '15 at 21:45
  • 1
    @D.W. We can build the tree in a DFS manner this way. Build a sorted list of the set of intervals according to Hendrik Jan's order, then using a stack, build the tree: to process the next element in the list, check why it is larger than the current one; if it is because it is a descendant, then it is a child - we put a copy of it on the stack and go down into the subtree rooted at the next item in the list. If it is because it comes later, then the current subtree is fully constructed, and we pop items from the stack until the top item on the stack is a superset of the next item in the list. – G. Bach Feb 6 '15 at 23:27
  • @G.Bach Thanks for showing it is indeed an answer. – Hendrik Jan Feb 7 '15 at 12:12

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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