日雇いの仕事（貪欲法）

問題

日雇いの仕事が $ N $ 件あります。

$ i $ 件目の日雇いの仕事を請けて働くと、その $ A_i $ 日後に報酬 $ B_i $ が得られます。

これから日雇いの仕事の中から１日に１件だけ選んで働くことができます。

ただし、一度請けたことのある日雇いの仕事をもう一度選ぶことはできません。

今日から $ M $ 日後まで（ $ M $ 日後を含む）に得られる 報酬の合計の最大値 を求めて下さい。

なお、日雇いの仕事は今日（０日後）から請けて働くことができます。

解法・ソースコード

まず報酬を最適化する方法として、次の２つが思い浮かびます。

🔹 報酬が多い仕事から選んでいく。
🔹 報酬を受け取るまでの期間が長い仕事から選んでいく。

しかしこの２つの方法では反例が見つかってうまくいきません。

この問題では、締め切りである $ M $ 日目から $ 0 $ 日目へとさかのぼるように考えるとうまくいきます。

解法としては次の通りです。

$ i = M - 1, M - 2, …, 0 $ に対して

🔹 残っている仕事のうち
🔹 $ A_i \leqq M - i $ である仕事であり
🔹 $ B_i $ が最大のもの

を $ i $ 日目に入れていきます。ただしそのような仕事がない場合はスキップします。

さらに、この解法を高速化するために ヒープ を使います。

$ i = M - 1, M - 2, …, 0 $ に対して

🔹 ヒープに $ A_i \leqq M - i $ であるような仕事を全て挿入する。
🔹 ヒープから $ B_i $ が最大のものを取り出す（ヒープから削除）。ただしヒープが空の場合はスキップする。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#--------- 入力例 ----------
m = 4           # M日後
# (days)日後に、(reward)の報酬を受け取れる仕事
jobs = [{'days':4, 'reward':3},
        {'days':4, 'reward':1},
        {'days':2, 'reward':2}]
#---------------------------
from heapq import heappush, heappop

# days_reward[v]：days[i] = v となる i に対する reward[i] の集合
days_reward = [[] for _ in range(m + 1)]
for job in jobs:
    # 報酬の支払いが M 日を超える場合はパス
    if job['days'] > m:
        pass
    else:
        # データ登録
        days_reward[job['days']].append(job['reward'])

res = 0     # 報酬の最大値
que = []    # ヒープ

# M - 1 日目から 0 日目へとさかのぼる(days_reward[0]から順に見る)
for reward in days_reward:
    for reward1 in reward:
        # ヒープは小さい順となるので符号反転して追加
        heappush(que, reward1 * -1)
    if que:
        x = heappop(que)
        res -= x

print('解：', res)

[実行結果]

解： 5

次のように仕事を請けることで、合計５の報酬を受け取ることができます。

🔹 今日（０日目）に $ 1 $ 件目の仕事を請けます。４日目に報酬 $ 3 $ を受け取れます。
🔹 明日（１日目）に $ 3 $ 件目の仕事を請けます。２日後の３日目に報酬 $ 2 $ を受け取れます。

したがって正解は報酬 $ 5 $ となります。