14-1 Point of maximum overlap

Suppose that we wish to keep track of a point of maximum overlap in a set of intervals—a point with the largest number of intervals in the set that overlap it.

a. Show that there will always be a point of maximum overlap that is an endpoint of one of the segments.

b. Design a data structure that efficiently supports the operations \(\text{INTERVAL-INSERT}\), \(\text{INTERVAL-DELETE}\), and \(\text{FIND-POM}\), which returns a point of maximum overlap. (\(\textit{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.)

(Removed)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用