18

時間間隔のリストが与えられた場合、重複しない最大間隔のセットを見つける必要があります。

例えば、

次の間隔がある場合：

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

また、時間は の範囲内にある必要があります[0000, 2400]。

重複しない間隔の最大セットは です[0600, 0830], [0900, 1130], [1230, 1400]。

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

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

4

1 に答える 1

28

これは NP 完全問題ではありません。O(n * log(n))この問題を解決するために動的計画法を使用するアルゴリズムを考えることができます。

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

  1. 前処理:

    • すべての間隔を開始点で並べ替えます。A[n]n 間隔 の配列を取得するとします。
      • このステップにはO(n * log(n))時間がかかります
    • 区間のすべての終点について、その後に続く最小の始点のインデックスを見つけます。整数 の配列を取得するNext[n]とします。n
      • そのような開始点が間隔の終了点に存在しない場合、 にi,割り当てることができnますNext[i]。
      • O(n * log(n))すべての間隔の n 個のエンドポイントを列挙し、二分探索を使用して答えを見つけることで、時間内にこれを行うことができます。これを解決するための線形アプローチが存在する可能性がありますが、前のステップにはすでにO(n * log(n))時間がかかるため、問題ではありません。

  2. 差出人:

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

上記の解決策は、問題を一目見ただけで思いついたものです。その後、より単純な貪欲なアプローチも考えます (ただし、大きな O 表記の意味で高速ではありません)。

(上記の DP アプローチと同じ表記法と仮定を使用)

  1. 前処理: すべての区間を終点で並べ替えます。B[n]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;
    }
}

上記の2つの解決策は私の頭から浮かびますが、あなたの問題は活動選択問題とも呼ばれ、Wikipedia http://en.wikipedia.org/wiki/Activity_selection_problemで見つけることができます。

また、Introduction to Algorithmsでは、この問題について 16.1 で詳しく説明しています。

于 2013-11-08T03:28:12.940 に答える