問題
日雇いの仕事が 件あります。
件目の日雇いの仕事を請けて働くと、その 日後に報酬 が得られます。
これから日雇いの仕事の中から1日に1件だけ選んで働くことができます。
ただし、一度請けたことのある日雇いの仕事をもう一度選ぶことはできません。
今日から 日後まで( 日後を含む)に得られる 報酬の合計の最大値 を求めて下さい。
なお、日雇いの仕事は今日(0日後)から請けて働くことができます。
解法・ソースコード
まず報酬を最適化する方法として、次の2つが思い浮かびます。
🔹 報酬が多い仕事から選んでいく。
🔹 報酬を受け取るまでの期間が長い仕事から選んでいく。
しかしこの2つの方法では反例が見つかってうまくいきません。
この問題では、締め切りである 日目から 日目へとさかのぼるように考えるとうまくいきます。
解法としては次の通りです。
に対して
🔹 残っている仕事のうち
🔹 である仕事であり
🔹 が最大のもの
を 日目に入れていきます。ただしそのような仕事がない場合はスキップします。
さらに、この解法を高速化するために ヒープ を使います。
に対して
🔹 ヒープに であるような仕事を全て挿入する。
🔹 ヒープから が最大のものを取り出す(ヒープから削除)。ただしヒープが空の場合はスキップする。
[Google Colaboratory]
1 | #--------- 入力例 ---------- |
[実行結果]
解: 5
次のように仕事を請けることで、合計5の報酬を受け取ることができます。
🔹 今日(0日目)に 件目の仕事を請けます。4日目に報酬 を受け取れます。
🔹 明日(1日目)に 件目の仕事を請けます。2日後の3日目に報酬 を受け取れます。
したがって正解は報酬 となります。