最大ジョブ時間を持つスケジュール時間表。

Question

私はいくつかの時間が設定されている（開始 - 終了）問題に取り組んでおり、ジョブの最大数が完了するようにリストを与える必要があります。

1. 私はDPを使用するソリューションを持っているとはOn2
に

をそれを解決することは、それは上で行うことができますか？

Answer 1

大丈夫、私はそれが詳細は欲張りアルゴリズム によって行うことができるソリューションました： http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec04-interval.pdf

Answer 2

は、（ジョブがJ1（S1、E1）、J2（S2、E2）、···、JNとしますsn、en） ここで、s1、s2、s3、...、snはジョブの開始時刻であり、 e1、e2、e3、...、enはジョブの終了時刻です。

（いずれかのアルゴリズムを使用してください） ジョブ＃（別の配列にジョブ＃を保存することもできます）。 ジョブの開始時刻を並べ替えると、対応するジョブ＃配列もソートします。

リストから最後のジョブを取り出して、最終回答リストに入れます。

リストを最後のジョブ から逆方向にスキャンし、最後のジョブがの場合は実行可能なジョブをチェックしてくださいはすでに撮影されています。このジョブの終了時刻は、最後のジョブの開始時刻以下です。このジョブを最終回答リストに追加します。

この作業でも同じ手順を実行します。このインデックスのリストをスキャンし、終了時刻が最終回答リストに最後に追加されたジョブの開始時刻以下になるようにジョブを取得します。あなたが完了するまでこれを繰り返します。

ここで、最終回答リストのジョブ数を数えてください。 これは実行できるジョブの最大数です。

手順全体がO（n lg n）+ O（n）時間かかる。 （基数ソートのような非比較ベースソートアルゴリズムを使用して開始時間をソートすると、複雑さはO（n）になります）を減らすことができます。