algorithm - イベントスケジューリング

Question

n個のジョブのセットが与えられます。各ジョブは、開始時刻と終了時刻に関連付けられており、どちらも整数で表され、それから得られる利益があります。一度に実行できるジョブは1つだけであることを念頭に置いて、利益を最大化するためにどのジョブを実行するかを決定する必要があります。O（n ²）よりも効率の良いアルゴリズムはありますか？

Answer 1

アルゴリズム:

与えられた集合 S = {I1,I2,...,In}:

• S の間隔を、開始時間の低いものから高いものの順に並べ替えます。

これでセット {J1,J2,...,Jn} が注文されました。(W1,W2,...,Wn を利益とする)

a(i) を最小インデックス k として定義します。このような Jk の開始時間は、Ji の終了時間よりも長くなります。誰も存在しない場合は -1 を返します。

セット{Ji、Ji+1、...、Jn}の最大利益（あなたが説明したように）としてD [i]を示します。

したがって、次のようになります。

D[-1] = 0;
D[i] = maximum{D[i+1],Wi + D[a(i)]}.

• D[0] を返します。

ランタイム：

n 間隔の並べ替え - O(nlogn)。

D - O(n) を構築します。

全体の実行時間 = O(nlogn)。

Answer 2

あなたが説明する問題は加重間隔スケジューリングと呼ばれ、O(nlogn) ステップで解決できます。ジョブが既にソートされている場合は O(n) でも解決できます。

クイック Google 検索で、必要なすべての情報が得られます。