间隔树查询

Question

给定一组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 now
}

for each Interval i:
    result[i.id] = query(root, i)

Answer 1

我们可以使用区间树来解决这个问题。

算法：

1. 构造一组点 S - 合并区间的所有左右点。对于示例 S = {0, 2, 3, 4, 5, 9} 的输入。复杂度 - O(NlogN)

2. 构建具有以下结构的区间树

   struct tree { int max_overlap_value; int max_overlap_id; int second_max_overlap_value; int second_max_overlap_id; tree *left; tree *right; };

   还设置 max_overlap_value = secondary_max_overlap_value = 0，max_overlap_id = secondary_max_overlap_id -1。复杂度 - O(N)

3. 使用输入的间隔更新树节点中的值。复杂度 - O(NlogN)

4. 对于每个间隔，查找 max_overlap_value、max_overlap_id、second_max_overlap_value、second_max_overlap_id。如果max_overlap_id等于interval_id，则使用second_max_overlap_value，否则使用max_overlap_value。复杂度 - O(NlogN)

总复杂度为O(NlogN)