Given a set of intervals, find the interval which has the maximum number of intersections
algorithm, data-structures
Solution
Note: David Eisenstat's algorithm has better performance than this one.
A simple plane-sweep algorithm will do this in `O(nlogn + m*n)`, where `m` is the maximum number of intersections with any single interval.
Sort the interval endpoints. Keep track of the active segments. When reaching a start point, increment the intersection counts of all active intervals, and set the new interval's intersection count to the number of active intervals (excluding itself). When reaching an end point, remove the interval from the active intervals.
Problem
Given a set of intervals, find the interval which has the maximum number of intersections (not the length of a particular intersection). So if input (1,6) (2,3) (4,11), (1,6) should be returned. Some suggest to use Interval Tree to get this done in O(nlogn), but I did not understand how to construct and use the Interval Tree after reading its wiki page. I believe it can be done by doing some sort of sorting and scanning algorithm. If Interval tree is the only option, please educate me how to construct/use one. Thanks.