Algorithms for finding the intersections of intervals

Question

I am wondering how I can find the number of intervals that intersect with the ones before it. we want to know he number of pairs (i, j), with i < j, such that Internal i ∩ interval j = ∅. For example for the intervals [2, 4], [1, 6], [5, 6], [0, 4], the output should be 2. from [2,4] [5,6] and [5,6] [0,4].

So now we have 1 set of intervals with size n all containing a point a, then we add another set of intervals size n as well, and all of the intervals are to the right of a. Can you do this in O(nlgn) and O(nlg^2n)?

Answer 1

You question is not very clear. You say that the intervals need to intersect and then go on to say the intersection is empty. Which is it?

In any case, since this is an interview question, my guess is Interval Trees are what you might need.

Good luck.

Answer 2

If the answer for the first paragraph is to be a collection of intervals, then look at the range tree and interval tree data structures and ignore the rest of what I have to say.

If the answer for the first paragraph is a simple count, then range tree and interval tree are not what you want, because the cost for a search there grows with the number of intersecting intervals found. However note that if i < j and interval i intersects with interval j then interval j intersects with interval i, so that if you were checking for intervals i, j such that i > j then you would still see a match. This means that the answer you get does not depend on the order in which you present the intervals so you can choose that to suit yourself.

Sort the intervals into order of increasing first co-ordinate and work through them one by one, keeping a queue of intervals seen so far ordered by decreasing second co-ordinate. When you see a new interval, remove from the queue all intervals previously seen that have a second co-ordinate that means it does not intersect with the new interval. The new interval will intersect with everything else, so accumulate the number of intersections found, add the new interval to the queue, and continue.

This gives you a count of the number of intersections in time n log n. If you want the number of non-intersections, subtract this from n(n-1)/2.