問題
$N$ 個のジョブが与えられる。ジョブ $i$ は開始時刻 $s_i$、終了時刻 $f_i$、利益 $v_i$ を持つ。互いに重複しないジョブの部分集合を選び、利益の総和を最大化せよ。
重複しないとは $f_i \le s_j$ または $f_j \le s_i$ が成り立つことをいう（端点が一致してもよい）。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N$ | $\le 5 \times 10^5$ | ジョブ数 |
| $s_i, f_i$ | $0 \le s_i < f_i \le 10^9$ | 時刻は整数 |
| $v_i$ | $1 \le v_i \le 10^9$ | 利益 |
入出力例
入力例1
6
0 3 3
1 4 2
2 5 1
3 6 4
4 7 2
5 8 6出力例1
10概念図: WIS の DP テーブルと二分探索
ヒント
ヒント1（方向性）
終了時刻でソートし、$dp[i]$ = 最初の $i$ 個のジョブを考慮したときの最大利益を定義する。漸化式は $dp[i] = \max(dp[i-1],\, v_i + dp[p(i)])$ で、$p(i)$ はジョブ $i$ と重複しない最大のジョブインデックス（$f_j \le s_i$ を満たす最大 $j$）。
ヒント2（アプローチ）
ソート後の終了時刻配列 finishes に対して bisect_right(finishes, s_i) を使えば $p(i)$ が $O(\log N)$ で求まる。全体 $O(N \log N)$。
ヒント3（ほぼ答え）
import bisect
jobs.sort() # 終了時刻でソート
finishes = [job[0] for job in jobs]
dp = [0] * (N + 1)
for i in range(1, N + 1):
f_i, s_i, v_i = jobs[i - 1]
# s_i 以下の終了時刻の最大インデックス
pi = bisect.bisect_right(finishes, s_i, 0, i - 1)
dp[i] = max(dp[i - 1], v_i + dp[pi])模範解答
import sys
import bisect
input = sys.stdin.readline
def solve():
N = int(input())
jobs = []
for _ in range(N):
s, f, v = map(int, input().split())
jobs.append((f, s, v))
jobs.sort() # 終了時刻でソート
finishes = [job[0] for job in jobs]
dp = [0] * (N + 1)
for i in range(1, N + 1):
f_i, s_i, v_i = jobs[i - 1]
pi = bisect.bisect_right(finishes, s_i, 0, i - 1)
dp[i] = max(dp[i - 1], v_i + dp[pi])
print(dp[N])
solve()Step-by-Step 解説
Step 1: ソートと DP の定義
終了時刻でソートすることで DP の順序（後ろのジョブが前のジョブに依存しない）を保証できる。
jobs.sort() # (finish, start, value) でソート
dp = [0] * (N + 1) # dp[0] = 0 が基底Step 2: p(i) の高速計算
| 方法 | 計算量 | 備考 |
|---|---|---|
| 線形探索 | $O(N)$ | 全体 $O(N^2)$ で TLE |
| 二分探索 | $O(\log N)$ | 全体 $O(N \log N)$ で OK |
Step 3: DP 遷移の意味
$dp[i] = \max(dp[i-1],\, v_i + dp[p(i)])$
dp[i-1]: ジョブ $i$ を選ばない場合v_i + dp[p(i)]: ジョブ $i$ を選ぶ場合（$p(i)$ 以前の最大利益に $v_i$ を加算）
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
bisect_left を使う | $s_i$ と等しい終了時刻を持つジョブが除外される | bisect_right(finishes, s_i) |
| dp を 0-indexed で管理 | $p(i)=0$ が「ジョブなし」を指せない | dp を 1-indexed にして dp[0]=0 を基底 |
| ソートを終了時刻でしない | DP の単調性が崩れる | jobs.sort() で終了時刻優先 |
bisect_right(finishes, s_i) の範囲指定なし | まだ追加されていない要素を参照 | bisect_right(finishes, s_i, 0, i-1) |
次のステップ
- 発展問題: 各ジョブに締切がある場合の EDF（Earliest Deadline First）スケジューリング最適化
- 参考: Kleinberg & Tardos "Algorithm Design" Ch.6 (Weighted Interval Scheduling)
自己評価
理解度: / /
自分の回答:
気づき・メモ: