Maximum interval overlaps using an interval tree [closed]

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. 开发者_如何学Python Closed 10 years ago.

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?

---

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.

---

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.