假设我们希望跟踪一组间隔中的最大重叠点 - 数据库中具有最大间隔数的点与其重叠。最大重叠点
a。显示总是有一个最大重叠点，它是其中一个段的终点。
b。设计一个有效支持INTERVAL-INSERT，INTERVAL-DELETE和FIND-POM操作的数据结构，它返回最大重叠点。 （提示：保留所有端点的红黑树，将值+1与每个左端点相关联，并将值-1与每个正确的端点相关联。使用一些额外信息增加树的每个节点以维护点的最大重叠）。
这个问题是在这本书中介绍的算法。但我不知道如何解决第二个问题。如果更大的头脑有一个优雅的解决方案，请与我分享您的想法！谢谢。
报价：http://ripcrixalis.blog.com/2011/02/08/clrs-chapter-14/
保留所有端点的RB-树。 我们逐个插入端点作为扫描线从左到右扫描。对于每个左端点e，将值p [e] = +1（将重叠增加1）。每个右端点e将一个值p [e] = -1（将重叠减1）。 当多个端点具有相同的值时，请在插入具有该值的任何右端点之前插入具有该值的所有左端点。
这里有一些直觉。让e1，e2，...。 。 。 ，en是与我们的间隔相对应的排序的端点序列。令s（i，j）表示对于1≤i≤j≤n，和p [ei] + p [ei + 1] + ... + p [ej]。 我们希望找到一个最大化s（1，i）。 每个节点x存储三个新属性。 我们存储v [x] = s（l [x]，r [x]），x的子树中所有节点值的总和。 我们还存储m [x]，这是通过表达式s（l [x]，i）获得的任何i的最大值。 我们将o [x]存储为m [x]达到其最大值的i的值。对于定点，我们定义v [零[T]] = M [零[T] = 0。
我们可以计算在一个底向上的方式这些属性以便满足定理14.1的要求：
v[x] = v[left[x]] + p[x] + v[right[x]] ,
m[x] = max{
m[left[x]] (max is in x’s left subtree),
v[left[x]] + p[x] (max is at x),
v[left[x]] + p[x] + m[right[x]] (max is in x’s right subtree). }
一旦我们理解了如何计算m [x]，从x及其两个孩子中的信息计算o [x]就很简单。
FIND-POM：返回端点由o [root [T]]表示的区间。由于我们如何定义新属性，定理14.1说每个操作都运行在O（lg n）时间。事实上，FIND-POM只需要O（1）次。
这看起来很像家庭作业。你有什么尝试？你认为你卡在哪里？ – 2013-02-08 19:55:53
尝试寻找贪婪算法 – 0x90 2013-02-08 19:56:55
该问题包含提示。这是你需要的想法。 – 2013-02-08 21:03:13