使用间隔树重叠最大间隔

Question

这是一个有趣的问题:给定一组N个区间([start,end]),使用区间树来查找重叠区间的最大数量.

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

实际上,Cormen等人的"算法导论"一书中的练习问题表明,这可以通过增加红黑间隔树来实现.有什么想法可以做到这一点？

Answer 1

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