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

0

O(RlogN) 時間を使用して解決できると思います。ここで、R は、特定のクエリ間隔 i と重複する間隔の最大数です。私のアプローチは、Balanced Binary Search Tree の実装に基づいて間隔ツリーを構築することです。間隔に基づいてツリーを構築したら、O(RlogN) 時間で実行できるクエリ間隔と重複する設定された間隔を見つける必要があります。これを行った後、O(R) 時間で最大重複間隔を見つけることができます。このアプローチの最悪の場合の複雑さは O(NlogN) です。

于 2014-10-26T23:14:59.700 に答える