10

間隔のセットが与えられた場合: {1-4, 6-7, 10-12} 新しい間隔: (9,11) を追加して、最終的な解が「マージ」されるようにします: 出力: {1-4, 6-7, 9-12}。合併は両側（低域と高域）で発生する可能性があります。

この質問が複数の場所で回答されているのを見ました。誰かが Interval Tress の使用を提案していましたが、正確にどのように使用するかについては説明していませんでした。私が知っている唯一の解決策は、間隔を開始時間の昇順に並べ、それらを繰り返し処理し、適切にマージしようとすることです。

このユースケースで間隔ツリーを使用する方法を誰かが理解するのを手伝ってくれれば、それは素晴らしいことです!

[私は CLRS の本でインターバル ツリーをたどってきましたが、それらはマージについては話していません。彼らが話しているのは、挿入と検索だけです。]

4

5 に答える 5

7

(これは、インターバルが決してオーバーラップできないことを意味すると仮定しています。そうしないと、マージされてしまうからです。)

これを行う 1 つの方法は、範囲の端点ごとに 1 つのノードを持つバランスのとれた二分探索木を格納することです。各ノードは、間隔の開始をマークする「オープン」ノードまたは間隔の終了をマークする「クローズ」ノードのいずれかとしてマークされます。

新しい範囲を挿入すると、範囲の開始点に関して次の 2 つのケースのいずれかが発生します。

  1. 既に範囲内にあるため、挿入の一部として既存の範囲を拡張することになります。
  2. 範囲内にないため、新しい「オープン」ノードを作成します。

どのケースにいるかを判断するには、範囲の開始点のツリーで先行検索を実行できます。NULL またはクローズ ノードを取得した場合は、範囲の開始点を表す新しいオープン ノードを挿入する必要があります。開いているノードを取得すると、その間隔を延長し続けるだけです。

そこから、範囲がどこまで広がるかを判断する必要があります。これを行うには、次のいずれかが発生するまで、挿入した最初のノードの後続ノードを継続的に計算します。

  1. ツリー内のすべてのノードを確認しました。その場合、この間隔の終わりを示す終了ノードを挿入する必要があります。

  2. 範囲の終わりの後に近いノードが表示されます。その場合、新しい範囲が終了したときに既存の範囲の真ん中にいるので、それ以上何もする必要はありません。あなたは終わった。

  3. 範囲の終わりの前に閉じたノードまたは開いたノードが表示されます。その場合、古い範囲が新しい範囲に含まれるため、そのノードをツリーから削除する必要があります。

  4. 範囲の終わりの後に開いているノードが表示されます。その場合、新しいクローズ ノードをツリーに挿入します。これは、この新しいクローズ ノードの開始を確認する前に、現在の範囲を終了する必要があるためです。

単純に実装すると、このアルゴリズムの実行時間は O(log n + k log n) になります。ここで、n は間隔の数、k はこのプロセス中に削除される間隔の数です (n 回の削除を行う必要があるため)。ただし、次のトリックを使用すると、これを O(log n) まで高速化できます。削除プロセスでは常にノードが順番に削除されるため、エンドポイントの後続検索を使用して、削除する範囲の最後を判別できます。次に、2 つのツリー分割操作と 1 つのツリー結合操作を実行することで、ツリーから削除するサブ範囲をスプライスできます。適切なバランスの取れたツリー (たとえば、赤黒またはスプレイ) では、これは O(log n) の合計時間で実行できます。これは、多くの範囲が含まれる場合にはるかに高速です。

お役に立てれば！

于 2013-01-27T09:01:55.120 に答える
1

パブリッククラス MergeIntervals {

public static class Interval {

    public double start;
    public double end;

    public Interval(double start, double end){
        this.start = start;
        this.end = end;
    }
}

public static List<Interval> mergeInteval(List<Interval> nonOverlapInt, Interval another){

    List<Interval> merge = new ArrayList<>();

    for (Interval current : nonOverlapInt){

        if(current.end < another.start || another.end < current.start){
            merge.add(current);
        }
        else{

            another.start = current.start < another.start ? current.start : another.start ;
            another.end = current.end < another.end ? another.end : current.end;                
        }           
    }
    merge.add(another);
    return merge;   
}
于 2015-10-08T22:20:18.730 に答える
0

これをチェックしてください。それはあなたを助けるかもしれません:- http://www.boost.org/doc/libs/1_46_0/libs/icl/doc/html/index.html

ライブラリは次の機能を提供します。

1) interval_set

2)separate_interval_set

3) split_interval_set

于 2013-01-27T08:32:24.820 に答える