小编inc*_*dow的帖子

给定一组N个区间:对于每个区间,哪个其他区间具有最大重叠？

例如{[0,5],[2,9],[2,3],[4,9]}:

[0,5]:[2,9](重叠4)

[2,9]:[4,9](重叠6)

[2,3]:[0,5]或[2,9](重叠2)

[4,9]:[2,9](重叠6)

N可以很大,所以我认为间隔树是必要的.但是,我发现的帖子或出版物都没有描述这种查询的方法.查询的结果可以位于间隔树节点(中心左侧,中心重叠,中心右侧)的3条路径中的任何一条路径上,因为它们可能包括也可能不包括查询间隔的中心点.因此,我无法想到获得结果的log(N)遍历方法.

另外,对于[2,3]的情况,我并不关心选择哪一个.可以任意挑选任何最大交叉间隔.每个查询只返回1个结果.

是否可以在log(N)中回答每个查询,提供Nlog(N)整体解决方案？

编辑:我编写的伪代码:

query(ITnode node, Interval intrv){
    // s_list: start-sorted intervals overlapping center
    // e_list: end-sorted intervals overlapping center
    if intrv.end < node.center:
        node_max = search node.s_list for interval w/ closest start to intrv.start
        return max(node_max, query(node.left_tree, intrv))
    else if intrv.start > node.center:
        node_max = search node.e_list for interval w/ closest end to intrv.end
        return max(node_max, query(node.right_tree, intrv))
    else: // Query overlaps center
        // Still working this out but I get the picture …