algorithm - 使用区间树的最大区间重叠

Question

这是一个有趣的问题：给定一组 N 个区间（[start, end]），使用区间树来找到重叠区间的最大数量。

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

事实上，Cormen 等人在“算法简介”一书中的一个练习问题表明，这可以通过增加红黑区间树来实现。任何想法如何做到这一点？

Answer 1

您可以在此处找到基于增强 AVL 自平衡树的区间树：http ://code.google.com/p/intervaltree/ 。它向您展示了如何做到这一点。你可以对红黑树做同样的事情。

Answer 2

一些例子来看看。您可以为此使用区间树。CGAL为您提供了一个强大的实现。另一个与您的问题类似的有趣示例。