9

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?

Community
  • 1
  • 1
stackoverflowuser2010
  • 38,621
  • 48
  • 169
  • 217
  • Are you interested in operations such as `Add(x, y) - add an interval to the tree`, `Query() - find the maximum number of overlapping intervals`? Do you also want `Del(x, y) - delete the interval [x, y] from the tree`? – IVlad Sep 20 '10 at 21:00
  • If the intervals are arranged in a balanced interval tree such as the one provided in Cormen's book, then we already know that Add(interval) and Delete(interval) run in O(lg N) time. So I would like to know how to use this tree to find the maximum number of overlapping intervals in preferably O(lg N) time. – stackoverflowuser2010 Sep 20 '10 at 21:07
  • Can you define overlapping? That is, do you mean a set of intervals with a point in common or do you mean a set of intervals such that there is an overlapping path between any pair? – Rafe Sep 21 '10 at 00:02
  • Overlapping here should mean that one interval's end time is >= the start time of another interval. – stackoverflowuser2010 Sep 21 '10 at 04:19

2 Answers2

-1

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.

cos
  • 97
  • 1
-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.

yadab
  • 2,063
  • 1
  • 16
  • 24