問題
N個の仕事がある。各仕事には「締め切り日 D_i」と「報酬 P_i」がある。1日に1つの仕事しかできず、仕事は締め切り日当日までに完了すればよい。報酬の合計を最大化したときの最大報酬を出力せよ。
入力形式
N
D_1 P_1
...
D_N P_N制約
$1 \le N \le 1000$
$1 \le D_i \le 1000$
$1 \le P_i \le 10^9$
入出力例
入力例 1
5
4 20
2 15
3 10
2 25
1 5出力例 1
60ヒント (段階的開示)
ヒント1: 方向性
「高報酬の仕事を優先して、できるだけ遅い日に割り当てる」貪欲戦略。
ヒント2: アプローチ
報酬降順にソートし、順に「締め切り以前の空いている最も遅い日」に割り当てる。日のスロットを配列で管理。
ヒント3: 誘導
jobs.sort(key=lambda x: -x[1]) # 報酬降順
slot = [False] * (max_day + 1)
for d, p in jobs:
for day in range(d, 0, -1):
if not slot[day]:
slot[day] = True
total += p
break模範解答 (Python)
N = int(input())
jobs = []
for _ in range(N):
d, p = map(int, input().split())
jobs.append((d, p))
jobs.sort(key=lambda x: -x[1])
max_day = max(d for d, p in jobs)
slot = [False] * (max_day + 1)
total = 0
for d, p in jobs:
for day in range(d, 0, -1):
if not slot[day]:
slot[day] = True
total += p
break
print(total)Step-by-Step 解説
1貪欲の方針
「報酬の高い仕事を優先する」＋「できるだけ締め切りギリギリに入れる」。早い日を空けておくと、他の仕事が入れる余地が増える。
「報酬の高い仕事を優先する」＋「できるだけ締め切りギリギリに入れる」。早い日を空けておくと、他の仕事が入れる余地が増える。
2スロット管理
slot[day] で各日の埋まり具合を管理。1-indexed のためサイズは max_day + 1。
3逆方向探索
range(d, 0, -1) で締め切り日から1ずつ減らして空き日を探す。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 締め切り超過に割り当て | range(1, d+1) で前向き | range(d, 0, -1) |
| 添字エラー | 0-indexedで混乱 | 1-indexed の方が直感的 |
| 降順ソート忘れ | 報酬最大化にならない | key=lambda x: -x[1] |
次のステップ
- 発展: 仕事の必要日数 T_i が加わる版（区間スケジューリング）