Job Sequencing Problem
n 個の仕事が 2 つの配列で与えられます。仕事 i は、時間 deadline[i] までに完了すると profit[i] の利益を得られます。各仕事にかかる時間は 1 単位で、時刻 0 から一度に 1 つの仕事を行い、任意の仕事をスキップできます。締め切りが 2 の仕事は、時刻 0 から 1 または時刻 1 から 2 まで実行できます。
得られる利益の合計の最大値を返してください。
関数
- deadlineinteger-array
- 各ジョブを完了しなければならない期限（1 から n まで）
- profitinteger-array
- 各仕事がどれだけ稼ぐか; profit[i] は deadline[i] に属する
- 戻り値integer
- すべての仕事を締め切りまでに完了できる場合の、最大の総利益
制約
1 ≤ deadline.length == profit.length ≤ 50001 ≤ deadline[i] ≤ n。ここで、nはジョブの数です。1 ≤ profit[i] ≤ 105- 配列はソートされていません。複数のジョブが同じ期限または利益を持つ場合があります。
例
- 入力
- deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
- 出力
- 120
- 説明
- 締め切り1の仕事は2つのうち1つしか入らないので、価値が50の仕事を実行します。価値が30の仕事は締め切り2に、価値が40の仕事は締め切り3に間に合います：50 + 30 + 40 = 120。
- 入力
- deadline = [1, 1, 1]profit = [5, 9, 7]
- 出力
- 9
- 説明
- 3つのジョブすべてを時刻1までに完了させる必要がありますが、それまでに収まるジョブは1つだけです。その中で最も価値が高いジョブの報酬は
9です。
- 入力
- deadline = [2, 1, 2]profit = [60, 50, 20]
- 出力
- 110
- 説明
- 価値が50のジョブを0から1まで実行し、価値が60のジョブを1から2まで実行すると、合計で110になります。価値が60のジョブを先に実行すると、価値が50のジョブは締め切りを過ぎてしまいます。
発展問題
ジョブ i にかかる時間が1単位ではなく duration[i] 単位だとしたらどうでしょうか？最も利益の大きいジョブを最初に選ぶことで、依然として合計の利益が最大になるでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
もし仕事を1つだけできるとしたら、最も利益の大きい仕事を選ぶでしょう。その仕事を最適なスケジュールから外す理由はあるでしょうか？
利益の大きい仕事から順に確認し、締め切り以前の時間枠に空きがあれば、それぞれの仕事を割り当てます。その中で最も遅い時間枠に割り当てることで、締め切りの短い仕事のために早い時間枠を空けておきます。
多くのスロットが予約済みになると、最新の空きスロットを1つずつ探すのは時間がかかります。各予約済みスロットが、その1つ前のスロットを指す素集合データ構造を保ちます。締め切りからポインターをたどると、最新の空きスロットに移動し、空きがなければ0に移動します。
解説
どの仕事を残し、いつ実行するかは自分で選びます。貪欲法のルールひとつで両方を決めます。利益の大きい仕事から順に選び、それぞれを締め切り以前で空いている最も遅い枠に入れます。空きがなければ、その仕事はスキップします。素集合データ構造を使えば、すでに埋まっている枠を一つずつ調べずに空き枠を見つけられます。
利益が大きい順に、空きスロットを探す
考え方
時間をスロットに分割します。スロット t は t-1 から t までで、締め切りが d の仕事はスロット 1 から d までを使うことができ、締め切りが n を超えることはありません。最も利益の大きい仕事から順に選んでも問題ありません。使えるすべてのスロットが埋まっている場合、そのいずれかのスロットに入っている仕事と入れ替えれば、少なくとも同じだけの利益が得られます。最も遅いスロットを選ぶのが安全なのは、締め切りの早い仕事が使えるのは早いスロットだけだからです。
コストはスキャンにあります。すべての締め切りが n の場合、k 番目の仕事は、すでに埋まっている k-1 個のスロットを通り過ぎます。これは約 n²/2、つまり n = 5000 のとき 1,250 万ステップです。
アルゴリズム
- 各ジョブを利益の大きい順に並べ、各締め切りをその利益と対応させておきます。
- すべてが false のフラグからなる
n + 1個の配列takenを作成します。 - 各ジョブについて、締め切りから
tを 1 まで減らしながら調べ、まだ使われていない最初のスロットで止めます。 - スロットが見つかったら、それを使用済みにし、ジョブの利益を
totalに加えます。 totalを返します。
def jobSequencing(deadline, profit):
n = len(deadline)
taken = [False] * (n + 1) # taken[t]: the time unit from t-1 to t is booked
total = 0
for i in sorted(range(n), key=lambda i: profit[i], reverse=True): # most profitable first
for t in range(deadline[i], 0, -1): # latest free slot first
if not taken[t]:
taken[t] = True
total += profit[i]
break
return total空きスロットの素集合データ構造を使い、利益の大きい順に貪欲に選ぶ
考え方
スキャンは同じ予約済みスロットを何度もたどります。スロット 0 から n までを対象とする素集合データ構造を使えば、それらをスキップできます。スロット t が空いている間は parent[t] = t とし、予約すると parent[t] = t-1 に設定します。これにより、締め切りからポインターをたどると、直近の空きスロットに到達します。スロット 0 に到達したら、残りはありません。パス半分化では、通過する各スロットのポインターを 2 つ先に向けるため、その後の探索は短くなります。
3 番目の例では、価値が 60 と 50 のジョブが、それぞれスロット 2 と 1 を予約します。価値が 20 で締め切りが 2 のジョブは、2 から 1、さらに 0 とたどり、スキップされます。
ソートには O(n log n) かかり、パス半分化を用いると各検索の償却計算量は O(log n) なので、全体の計算量は O(n log n) のままです。
アルゴリズム
- 仕事を利益の大きい順に並べ、各締め切りを利益と対応させておきます。
- 0から
nまでの各スロットtについて、parent[t] = tを設定します。 - 各仕事について、
slot = deadlineから始め、parent[slot] == slotになるまでparentをたどり、その過程で経路を半分にします。 slot > 0の場合は、その仕事の利益を加算し、parent[slot] = slot-1を設定します。それ以外の場合は、その仕事をスキップします。- 合計を返します。
def jobSequencing(deadline, profit):
n = len(deadline)
# following parent from slot t ends at the latest free slot at or before t; 0 means none is left
parent = list(range(n + 1))
total = 0
for i in sorted(range(n), key=lambda i: profit[i], reverse=True): # most profitable first
slot = deadline[i]
while parent[slot] != slot:
parent[slot] = parent[parent[slot]] # halve the path as you go
slot = parent[slot]
if slot > 0:
total += profit[i]
parent[slot] = slot - 1 # booked: its chain continues at the slot before it
return total
落とし穴と境界ケース
- ジョブを最も早い空きスロットに入れること。3つ目の例では、価値が60のジョブがスロット1を使い、価値が50のジョブは実行できなくなるため、110ではなく80になります。
- 締め切り順にジョブを選ぶこと。締め切りが
[1, 1]、利益が[1, 100]の場合、利益の少ないジョブが唯一のスロットを使ってしまい、100ではなく1しか得られません。 - スロット配列のサイズを
n + 1ではなくnにすること。すると、締め切りがnの場合に配列の範囲外を読み取ります。 - 利益だけを並べ替えること。各締め切りは対応する利益と一緒に移動させる必要があります。
- 再帰でfindの手順を書くこと。予約済みスロットが何千個も連なるとスタックがあふれる可能性があるため、ループを使ってください。
よくある質問3
ジョブスケジューリング問題の時間計算量はどのくらいですか？
素集合データ構造を使うと、時間計算量はソートが支配的なため O(n log n)、空間計算量は O(n) です。空きスロットを探して各締め切りから逆方向に走査すると、締め切りの大半が大きい場合、O(n²) のコストがかかります。
ジョブスケジューリングで貪欲法がうまくいくのはなぜですか？
最適なスケジュールの中には、最も利益の大きい仕事が含まれています。その仕事が含まれておらず、締め切り前のスロットが空いていれば、それを追加することで利益が増えます。該当するスロットがすべて埋まっていれば、別の仕事と入れ替えることで少なくとも同じ利益が得られます。残りの仕事についても同じ議論を繰り返します。
ジョブのスケジューリングは、代わりにヒープを使って解決できますか？
はい。仕事を締め切り順に並べ、各利益を最小ヒープに追加します。ヒープ内の仕事数が現在の締め切りで許される数を超えたら、最小の利益を取り出します。最後にヒープには最適な仕事の集合が残り、その合計が答えになります。計算量は O(n log n) です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def jobSequencing(deadline, profit):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
deadline = [3, 1, 2, 3, 1] profit = [40, 35, 30, 25, 50]
期待される出力
120