オーバーラッピング間隔をマージするアルゴリズム

Question

間隔の動的配列にオーバーラッピング間隔をマージする効率的なアルゴリズムを探しています。例えば、ワイズ（時刻、終了時刻を開始）、

[(1, 2), (4, 8), (3, 10)]

は、（4,8）及び（3,10）が重なっているので、合流後

[(1, 2), (3, 10)]

なります。オーバーラッピングとは、2つの区間のいずれかの部分が同じ瞬間を共有することを意味します。

私は完全な配列が与えられたとき、開始時間の昇順（reference: geeksforgeeks）で間隔をソートした後にスタックで操作を実行できることを知ります。しかし、このアルゴリズムは、指定された配列が非動的である場合にのみ効果的に適用できますが、動的配列に対して効率的なものを探しています。たとえば、配列の間隔は頻繁に更新され、挿入され、間隔は各操作でマージされます。

Answer 1

インターバルの開始点であるキーを持つインターバルのバイナリ検索ツリー（BST）を保持します。挿入されるべき新しい間隔の

：

• 新しい間隔（（ログn）Oで行うことができる）の起点よりも小さいBSTで最大値を探します。

  この間隔または次の間隔は、新しい間隔と重複するか、または重複がありません（この場合、挿入を行うだけです）。

• 新しい間隔とオーバーラップする間隔が増える可能性がありますので、ここからBSTの残りの部分を繰り返し（上記の点から開始して）、その間隔を重複する間隔でマージする必要があります。

任意のインサートは（場合にその間隔は例えばで他のすべての間隔とオーバーラップ）最悪の場合（N Nログ）Oを取ることができるが、償却時間インサートあたりO（ログn）（以降であろう要素を削除するために実行された作業を、挿入するために実行された作業の一部としてカウントすることができます。これは、合計でO（log n）の作業です。これを行う

一部軽くテストしたC++コード：

// set<pair<int, int> > can also be used, but this way seems conceptually simpler 
map<int, pair<int, int> > intervals; 

void insert(int left, int right) 
{ 
    if (!intervals.empty()) 
    { 
    // get the next bigger element 
    auto current = intervals.upper_bound(left); 
    // checking if not found is not needed because of decrement and how C++ iterators work 
    // decrement to get next smaller one instead, but only if we're not that the beginning 
    if (current != intervals.begin()) 
     --current; 
    // skip current if it's entirely to the left of the new interval 
    if (current->second.second < left) 
     ++current; 
    // update new starting point if there's an overlap and current is more to the left 
    if (current != intervals.end() && current->first <= right) 
     left = min(left, current->first); 
    // iterate through while there's an overlap (deleting as we go) 
    for (; current != intervals.end() && current->first <= right; 
      current = intervals.erase(current)) 
     // update the end point of new interval 
     right = max(right, current->second.second); 
    } 
    // insert our updated interval 
    intervals[left] = make_pair(left, right); 
} 

// FYI: current->first is the start, current->second.second is the end 

Live demo。