インターバルツリー内のオーバーラップしないインターバルの最大値

Question

時間間隔のリストが与えられた場合、オーバーラップしない最大間隔のセットを見つける必要があります。例えば

、

我々は次のような間隔を持っている場合：

[0600, 0830], [0800, 0900], [0900, 1100], [0900, 1130], 
[1030, 1400], [1230, 1400] 

また、それはその時与えられた範囲[0000, 2400]にする必要があります。

最大オーバーラップしないインターバルのセットは[0600, 0830], [0900, 1130], [1230, 1400]です。

最大セット梱包はNP完全であることを理解します。私の問題（開始時刻と終了時刻のみを含む間隔）もNP-Completeであるかどうか確認したい。

もしそうなら、指数関数的な時間で最適解を見つける方法がありますが、よりスマートな前処理と枝刈りデータがあります。または、固定パラメータの扱いやすいアルゴリズムを実装するのが比較的簡単な場合。私は近似アルゴリズムに行きたくありません。

Answer 1

これはNP完全な問題ではありません。この問題を解決するために動的プログラミングを使用してO(n * log(n))アルゴリズムを考えることができます。

n個の区間があるとします。与えられた範囲がS（あなたの場合は、S = [0000, 2400]）であるとします。すべての間隔がSの範囲内にあると仮定するか、または線形時間でSの範囲内にないすべての間隔を削除します。

1. プリプロセス：彼らの開始ポイントによって

   • ソートすべての間隔。 n間隔の配列A[n]が得られたとします。
     • この工程は、後に、次の点を開始する最小のインデックスを見つけ、O(n * log(n))時間間隔のすべてのエンドポイントについて
   • とります。配列Next[n]がnの整数であるとします。
     • i,の終了点に対してこのような開始点が存在しない場合、nをNext[i]に割り当てることができます。
     • すべての間隔のn個のエンドポイントを列挙し、バイナリ検索を使用して答えを見つけることによって、O(n * log(n))時間にこれを実行できます。たぶん、これを解決するための線形アプローチが存在するかもしれませんが、前のステップはすでにO(n * log(n))時間かかるので問題はありません。

2. DP：

   • 範囲[A[i].begin, S.end]における最大非重複間隔がf[i]であると仮定する。その後、f[0]が私たちが望む答えです。
   • また、f[n] = 0とします。
   • 状態遷移方程式：
     • f[i] = max{f[i+1], 1 + f[Next[i]]}
   • DPのステップは、線形時間がかかるということは明白です。

上記の溶液は、私は、問題の一見を思い付くものです。 （上記DPのアプローチと同じ表記と仮定して）

1. ：その後、私はまた、より単純な（ランダウの記号の意味ではなく、より速い）で貪欲なアプローチを考えます前処理：すべての間隔をエンドポイントで並べ替えます。 n間隔の配列B[n]が得られたとします。貪欲

2. ：

   int ans = 0, cursor = S.begin; 
   for(int i = 0; i < n; i++){ 
       if(B[i].begin >= cursor){ 
        ans++; 
        cursor = B[i].end; 
       } 
   } 
   

上記の二つの解決策は、私の心から出てくるが、あなたの問題はまた、ウィキペディアhttp://en.wikipedia.org/wiki/Activity_selection_problemで見つけることができる活動選択問題、と呼ばれています。

また、アルゴリズムの紹介では、この問題が16.1で詳しく説明されています。