1

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 ?

Improve this question
1
  • Are you trying to see if each interval is inside of other intervals completely or if they just overlap? Commented Feb 6, 2010 at 5:29

3 Answers 3

Reset to default
2

Hint: sort the list.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Tried it. I cant sort it in nlogn (quick sort), but afterwards I still can't find a decent solution which works in less then n^2
What did you try to do after sorting the list, and what was the problem?
After I sorted the array, I tried searching for each a's b part, but in this way, you go through the array a times, hence, you get an algorithm with the efficiency of O(n*n).
@Idan: It is possible to search in a sorted list in log(n)
1

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.

Improve this answer

2 Comments

It is generally considered bad form to do someone's homework for him. A better idea is to give guidance and help the poster understand the concepts he needs to be able to arrive at the answer on his own.
thanks for the tips... frankly, I'm not sure i understand how you suggest that i should insert nodes to the tree... but i appreciate the effort
1
  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.
Improve this answer

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.