Algorithm for finding intervals inside an array

Question

Hello,

I have a list which contains n intervals [0,1]

each interval looks like [a(i),b(i)] 0<=a(i)<b(i)<=1 , i = 1...n

I need to find an efficient algo determining for each of the n intervals if it's contained inside other intervals.

I tried many option but i can only find one in O(n^2)

Any suggestions ?

Answer 1

Hint: sort the list.

Answer 2

Assume there is just one interval of [0,1]. Add it if it is not already in your list just for convenience.

Sort the endpoints. Where two endpoints are equal, sort them in reverse on the corresponding right endpoints. So [0.1, 0.2], [0.1, 0.3] would be sorted 0.1, 0.1, 0.2, 0.3, where the first 0.1 goes with the second interval. Similarly if the right endpoints are equal.

Each endpoint should have a reference to its interval so you can find the interval given an endpoint.

Scan the sorted endpoints. As you do, build a tree. Use [0,1] as the root. Nodes may be red or green. They start as red. So the root node is initially red.

The idea of the tree is that ultimately, if one interval contains another, it will be its ancestor in the tree. If two intervals do not overlap, or partially overlap, they will be in different branches and their only common ancestor will be the root, or some other interval that contains them both.

As each left endpoint is encountered it is added to a tentative location in the tree by adding a red node for its interval to the current tree node. So the first endpoint we encounter results in the corresponding interval being added under the root, and it becomes the current node. So, prior to its right-hand endpoint being encountered, a tree node may have several nodes attached to it.

When a right-hand endpoint is encountered, its node turns green, because we have covered it completely from one end to the other. If it has any red offspring, they have to be moved, because, while the just-turned-green node contains their left ends, it does not contain their right ends. So we move them all up to the parent node (which must still be red).

We continue this process until we get to the 1.0 endpoint. At this point the tree is complete. all nodes are green. The nodes under each node represent the intervals that the corresponding interval contains.