Algorithms for finding the intersections of intervals

Posted by tomwu on Stack Overflow See other posts from Stack Overflow or by tomwu
Published on 2010-06-08T02:07:13Z Indexed on 2010/06/08 2:12 UTC
Read the original article Hit count: 172

I am wondering how I can find the number of intervals that intersect with the ones before it. 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)?

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about interview-questions