最大重叠点 [英] Point of Maximum Overlap
问题描述
假设我们希望跟踪一组间隔中最大重叠的点-数据库中间隔最大的点与该点重叠.
Suppose that we wish to keep track of a point of maximum overlap in a set of intervals—a point that has the largest number of intervals in the database overlapping it.
a.证明总会有一个最大重叠点，该重叠点是这些分段之一的终点.
a. Show that there will always be a point of maximum overlap which is an endpoint of one of the segments.
b.设计一个有效支持操作INTERVAL-INSERT，INTERVAL-DELETE和FIND-POM的数据结构，该操作将返回最大重叠点.(提示:保留所有端点的红黑树.将值+1与每个左端点相关联，将值-1与每个右端点相关联.用一些额外的信息增强树的每个节点，以维护树的端点.最大重叠点.)
b. Design a data structure that efficiently supports the operations INTERVAL-INSERT, INTERVAL-DELETE, and FIND-POM, which returns a point of maximum overlap. (Hint: Keep a red-black tree of all the endpoints. Associate a value of +1 with each left endpoint, and associate a value of -1 with each right endpoint. Augment each node of the tree with some extra information to maintain the point of maximum overlap.)
此问题在算法简介一书中.但是我不知道如何解决第二个问题.如果有更大的想法可以解决问题，请与我分享您的想法！谢谢.
this problem is in the book introduction to algorithm. But I have no idea how to solve the second question. if a greater mind has an elegant solution, please share your idea with me! Thanks.
推荐答案
Keep a RB-tree of all the endpoints. We insert endpoints one by one as a sweep line scaning from left to right. With each left endpoint e, associate a value p[e] = +1 (increasing the overlap by 1). With each right endpoint e associate a value p[e] = −1 (decreasing the overlap by 1). When multiple endpoints have the same value, insert all the left endpoints with that value before inserting any of the right endpoints with that value.
这是一些直觉.设e1，e2，...，是与我们的间隔相对应的端点的排序顺序.令s(i，j)表示1≤i≤j≤n的总和p [ei] + p [ei + 1] +··+ p [ej].我们希望找到一个使s(1，i)最大化的i.每个节点x存储三个新属性.我们存储v [x] = s(l [x]，r [x])，即x子树中所有节点的值之和.我们还存储m [x]，这是通过表达式s(l [x]，i)获得的任何i的最大值.我们将o [x]存储为m [x]达到最大值的i的值.对于前哨，我们定义v [nil [T]] = m [nil [T]] = 0.
Here is some intuition. Let e1, e2, . . . , en be the sorted sequence of endpoints corresponding to our intervals. Let s(i, j) denote the sum p[ei] + p[ei+1] + · · · + p[ej] for 1 ≤ i ≤ j ≤ n. We wish to find an i maximizing s(1, i ). Each node x stores three new attributes. We store v[x] = s(l[x], r [x]), the sum of the values of all nodes in x’s subtree. We also store m[x], the maximum value obtained by the expression s(l[x], i) for any i. We store o[x] as the value of i for which m[x] achieves its maximum. For the sentinel, we define v[nil[T]] = m[nil[T]] = 0.
我们可以自下而上地计算这些属性，以满足定理14.1的要求:
We can compute these attributes in a bottom-up fashion so as to satisfy the requirements of Theorem 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].
Once we understand how to compute m[x], it is straightforward to compute o[x] from the information in x and its two children.
FIND-POM:返回以o [root [T]]表示端点的间隔.由于我们是如何定义新属性的，因此定理14.1表示每个操作都在O(lg n)时间中运行.实际上，FIND-POM仅花费O(1)时间.
FIND-POM: return the interval whose endpoint is represented by o[root[T]]. Because of how we have deÞned the new attributes, Theorem 14.1 says that each operation runs in O(lg n) time. In fact, FIND-POM takes only O(1) time.
这篇关于最大重叠点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
