4

これは、重なり合う間隔を見つけることに関連しています。間隔のリスト（間隔ツリー）が与えられた場合、その方法を知っています。私が持っているのは、間隔のリストのリストです。例えば、

[2,6], [7,11]
[1,3], [5,10], [11,13]
[2,5], [6,8]

この結果は次のようになります。

[2,3]、[7,8]

私がしなければならないことは、すべてのリストに共通する間隔のリストを見つけることです。

この問題は、リストのマージに似ていると思いnます。問題は、リストのペアごとのマージを適用できないことです。この方法を適用すると、重複する間隔が失われる可能性があります。したがって、すべてのリストを一度に (ペアごとではなく) 考慮して、すべてのリストをマージする必要があります。

インターバルツリーを使用できます。各リストの最初の間隔を間隔ツリーに挿入し、オーバーラップを見つけます。ツリーから最も弱い間隔を削除し、リストの 1 つから次の間隔を挿入します。この方法をどのように使用できるかはまだ完全にはわかりませんが、コストがかかりすぎるようです。

間隔のリストのリストから重複する間隔を見つけるための効率的なアルゴリズムはありますか?

追加情報: リスト内の間隔はソートされます。それらは重複せず、シーケンスを形成します。

4

3 に答える 3

4

単一の並べ替えられたトランジションの配列を作成します。各トランジションには位置があり、参加または退出する間隔の数に基づいた累積数があります。リストを通過するときは、自分がいくつのインターバルにいるのかを追跡します。シリーズと同じ数のインターバルにいるとき、それは共通のインターバルにいるときです。

あなたの例では、遷移は次のようになります。

[2, 1], [6, -1], [7, 1], [11, -1],
[1, 1], [3, -1], [5, 1], [10, -1], [11, 1], [13, -1]
[2, 1], [5, -1], [6, 1], [8, -1]

位置で並べ替えてマージすると、次のように折りたたまれます。

[1, 1], [2, 2], [3, -1], [5, 0], [6, 0], [7, 1], [8, -1], [10, -1], [11, 0], [13, -1]

これにより、次の累計の推移が得られます。

[1, 1], [2, 3], [3, 2], [7, 3], [8, 2], [10, 2], [13, 1]

2そして、3 にある間隔を、 から始まり に向かう間隔と3、 から始まりに7向かう間隔として読み取ることができます8。これが答えです。

1 つの長いリストを作成して並べ替えるというアイデアは、確かに余分な作業です。代わりに、これらのリストを作成して、その場でマージすることができます。節約は、イベント数のログではなく、シリーズ数のログの要因です。

于 2013-08-22T07:38:46.477 に答える
2

間隔の個々のリストはソートされており、重複していないと言いました。そう、

Keep track of where you are in each list, starting at the beginning of each.
While none of the lists has run out:
    If the current intervals (one from each list) all overlap:
       Output the intersection of the current intervals
    Find which of the current intervals has the earliest end point
    Advance one position within that list.

間隔の K 個のリストと N 個の間隔が全部である場合、最も簡単な方法で実装すると O(NK) 時間かかるはずですが、現在のヒープまたはその他の優先キューの間隔。

于 2013-08-22T15:31:06.083 に答える