Algorithm for finding intervals inside an array

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 ?

Hint: sort the list.

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.

1. Sort the intervals according to their start points breaking ties such that earlier endpoints appear later
2. Observe that in the sorted order, for every element e, an interval containing e can only exist to its left.
3. Hence linearly scan from the left keeping track of the maximum endpoint observed till now. At any stage, if endpoint of the current interval is less than the maximum endpoint, we have found an interval that is contained inside some other.