使用间隔树的最大间隔重叠 [英] Maximum interval overlaps using an interval tree

问题描述

这是一个有趣的问题：给定一组N个间隔（[开始，结束]），请使用间隔树查找重叠间隔的最大数量。

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.

一个类似的问题在StackOverflow上提供了O（N）解决方案，但是如果我们可以将间隔预处理为间隔树，也许我们可以找到对数时间的解决方案。

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.

实际上，Cormen等人在算法简介一书中的一个练习题表明，这可以通过增加红黑间隔树来实现。有什么想法可以做到吗？

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?

推荐答案

您可以在此处找到基于增强AVL自平衡树的间隔树：< a href = http://code.google.com/p/intervaltree/ rel = nofollow> http://code.google.com/p/intervaltree/ 。它向您展示了如何完成。您可以对一棵红黑树做同样的事情。

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.

这篇关于使用间隔树的最大间隔重叠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！