問題
$N$ 本の仕事 $(s_i, e_i, w_i)$ から重複しない部分集合を選び利益最大化せよ。
制約
$1 \le N \le 2 \times 10^5$
$0 \le s_i < e_i \le 10^9$
$1 \le w_i \le 10^9$
入出力例
入力例 1
5
1 3 50
2 5 60
3 6 70
4 7 80
6 9 90出力例 1
210[1,3,50] + [3,6,70] + [6,9,90] = 210
ヒント (段階的開示)
ヒント1: 方向性
終了時刻ソート + DP。
ヒント2: アプローチ
dp[i] = w[i] + max(dp[j] | e[j] <= s[i])、二分探索で前の仕事を $O(\log N)$ 検索。ヒント3: 実装
bisect_right(ends, s_i, 0, i) - 1 で適切な前仕事を特定。模範解答 (Python)
import sys
import bisect
input = sys.stdin.readline
def solve():
N = int(input())
jobs = []
for _ in range(N):
s, e, w = map(int, input().split())
jobs.append((e, s, w))
jobs.sort()
dp = [0] * (N + 1)
ends = [j[0] for j in jobs]
for i in range(N):
e_i, s_i, w_i = jobs[i]
k = bisect.bisect_right(ends, s_i, 0, i) - 1
dp_with = dp[k + 1] + w_i
dp[i + 1] = max(dp[i], dp_with)
print(dp[N])
solve()Step-by-Step 解説
1ソート
終了時刻昇順。これで「仕事 $i$ より前に終わったもの」だけが選択候補。
終了時刻昇順。これで「仕事 $i$ より前に終わったもの」だけが選択候補。
2DP 定義
$dp[i]$ = 最初 $i$ 仕事を検討した最大利益。選ぶ/選ばないの2択。
$dp[i]$ = 最初 $i$ 仕事を検討した最大利益。選ぶ/選ばないの2択。
3二分探索
bisect_right(ends, s_i, 0, i) - 1 で $e[j] \le s_i$ の最大 j を $O(\log N)$。4遷移
dp[i+1] = max(dp[i], dp[k+1] + w_i)5出力
dp[N]よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 境界条件 ($e_j = s_i$) | 等号OK／NGの混同 | 等号 OK で重複しないなら e[j] <= s_i |
| 開始時刻でソート | 順序条件が成り立たない | 終了時刻でソート |
| bisect 範囲外 | hi 未指定 | hi=i |
| 0/1-indexed 混同 | dp の管理 | dp は 1-indexed (dp[0]=0) |
次のステップ
- 最大 $K$ 本選択（$K \le 100$）
- 無制限ナップサック型変形