Maximum overlap point
Suppose we want to keep track of the point of maximum overlap in a set of bins — the point that has the most bins in the database that overlap it.
and. Show that there will always be a point of maximum overlap, which is the end point of one of the segments.
b. Create a data structure that effectively supports INTERVAL-INSERT, INTERVAL-DELETE, and FIND-POM operations that return the point of maximum overlap. (Hint: keep a red-black tree of all endpoints. Map a value of +1 to each left endpoint, and map a value of -1 to each right endpoint. Expand each node of the tree with some additional information to keep the point of maximum overlap.)
this problem is in the book on the algorithm. But I don't know how to solve the second question. if the bigger mind has a neat solution, please share your idea with me! Thank.
source to share
quote: http://ripcrixalis.blog.com/2011/02/08/clrs-chapter-14/
Save the RB tree of all endpoints. We insert the end points one by one as a flat pattern, looking from left to right. With each left endpoint e, associate the value p [e] = +1 (increasing the overlap by 1). With each right endpoint e, associate the 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.
Here are some intuitions. Let e1, e2,. ,, en be a sorted sequence of end points corresponding to our intervals. Let s (i, j) denote the sum p [ei] + p [ei + 1] + ··· + p [ej] for 1 ≤ i ≤ j ≤ n. We want 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 the xs subtree. We also store m [x], the maximum value obtained by s (l [x], i) for any i. We store o [x] as the value of i for which m [x] reaches its maximum. For the sentry, we define v [nil [T]] = m [nil [T]] = 0.
We can compute these attributes from the bottom up 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). }
Once we understand how to compute m [x], it is easy to compute o [x] from information from x and its two children.
FIND-POM: Return an interval whose ending point is represented by o [root [T]]. Because of the way we defined the new attributes, Theorem 14.1 says that each operation takes O (lg n) time. In fact FIND-POM only takes O (1) time.
source to share