間隔スケジューリング（典型的ではない）：すべてのスケジュールされた間隔の合計長を最大にする。

Question

（1,3）（2,4）（3,6）（4,7）、競合が存在しないようにスケジュールを探し、予定された間隔の合計長が最大である。

欲張りの解決策などのトピックについて話し合ったときに、「インターバルスケジューリング」タイプの質問を学習しました&学校での動的プログラミング。私は解決策がスケジューリングの具体的な目標に依存していることを知っています。可能な限り間隔==>貪欲。

しかし、この質問のために、私はブルートフォース（列挙）に頼らなければならないと思いますか？ 助けてください

Answer 1

あなたの提案された問題はまだ貪欲な方法で解決することができます。元のインターバルスケジューリングの問題を知っているので、質問文で述べた内容に基づいて解決策を作成します。

手順1：開始時刻に基づいて間隔をソートします。

ステップ2： 2タプルヒープを使用してデータ構造を維持する「スポーン」プールを維持します。

のは、我々はNが... I[N-1]を間隔I[0]をソート持っていると仮定しましょう、ステップ2で、より正確には、各Iはstartとstop属性を持っているので、I[i].start <= I[i+1].start。 2タプルのヒープがあり、各タプルは(T, M)を表します。 Tはヒープを離れる時間、または等価的には間隔の停止時間を意味します。 Mは、この間隔が選択された場合の最大電流カバレッジを表す。ヒープの順序はTによって維持されることに注意してください。変数ANSが維持され、現在の最大カバレッジを維持します。したがって、このアルゴリズムは次のように実行します：ここに

ANS <- 0 
HEAP <- [empty] 
for each sorted intervals `I[i]`: 
    while HEAP.empty() == false && HEAP.first_element.T < I[i].start 
     TMP = HEAP.first_element 
     HEAP.pop_first_element 
     if TMP.M > ANS 
      ANS = TMP.M 
    HEAP.insert((I[i].stop, ANS + I[i].stop - I[i].start))