Maximum interval overlaps using an interval tree [

问题:

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?

回答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.

回答2:

you can find an interval tree based on an augmented AVL self balancing tree here: http://code.google.com/p/intervaltree/ . it shows you how it can be done. you can do the same to an red-black tree.