5

给定一组 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)
4

2 回答 2

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 = second_max_overlap_value = 0, max_overlap_id = second_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)

于 2014-03-11T10:12:48.060 回答
0

我相信它可以使用 O(RlogN) 时间来解决，其中 R 是给定查询间隔 i 的最大重叠间隔数。我的方法是建立一个基于平衡二叉搜索树实现的区间树。一旦我们根据间隔构建树，我们必须找到与查询间隔重叠的设置间隔，这可以在 O(RlogN) 时间内完成，因为找到“a”重叠间隔是 logN 时间。在我们这样做之后，我们可以在 O(R) 时间内找到最大重叠间隔。这种方法的最坏情况复杂度是 O(NlogN)。

于 2014-10-26T23:14:59.700 回答