Maximum interval overlaps using an interval tree

Question

Here is an interesting question: Given a set of N intervals ([start, end]), use an interval tree to find the maximum number of overlapping intervals.

A similar question on StackOverflow provided an O(N) solution, but if we can pre-process the intervals into an interval tree, perhaps we can find the solution in logarithmic time.

In fact, an exercise problem in the "Introduction to Algorithms" book by Cormen, et al., suggests that this is possible by augmenting a red-black interval tree. Any ideas how this can be done?

Answer 1

Some example to look. You may use interval tree for this. CGAL gives you a robust implementation for this. Another interesting example similar to your problem.