首页 > 试题广场 >

（最大重叠点）假设我们希望记录一个区间集合的最大重叠点（a

[问答题]

（最大重叠点）假设我们希望记录一个区间集合的最大重叠点（a point of maximum overlap），即被最多数目区间所覆盖的那个点。

a.证明：最大重叠点一定是其中一个区间的端点。

b.设计一个数据结构，使得它能够有效地支持INTERVAL-INSERT,INTERVAL-DELETE，以及返回最大重叠点的FIND-POM操作。（提示：使红黑树记录所有的端点。左端点关联+1值，右端点关联-1值，并且给出树中的每个节点扩张一个额外信息来维护最大重叠点。）

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

上传者：小小

难度：

0条回答 0收藏 915浏览

扫一扫，把题目装进口袋