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: 173
algorithm
|interview-questions
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