貪欲法
01 / 共通の仕組み
各ステップで局所最適を確定し、その確定が後で覆らないことを示す。 バックトラックも DP テーブルも要らない:交換論法でどの貪欲な選択を入れ替えても 改善できないと示すか、先行論法で貪欲がどの接頭辞でも遅れないと示す。 この発想を 3 つの古典的サブパターンに落とし込む: 区間でソートして取る、配列上で到達範囲を追う、累積量で「失敗したらリセット」。
01 / 一文での本質
区間を終点でソートし、左から右へ走査して、 始点が直近に採用した終点を超えている区間を順に取る。 交換論法が示すとおり、最早終了の選択は常に安全 —— 他に替えても同等以下にしかならない。
問題最大の非重複区間数入力[1,3] [2,5] [3,6] [5,9] [8,12]
入力は 5 区間で与えられた順。貪欲のアイデア:終点でソートし、走査して、始点が直近の採用終点を超える区間を順に取る。
ステップ
0 / 12
採用
—
直近終点
−∞
0 / 12
02 / パターンの骨格
# 終点でソート — 始点ではないintervals.sort(key=lambda iv: iv.e)result ← []; lastEnd ← −∞for iv in intervals:if iv.s ≥ lastEnd:result.push(iv) # 採用lastEnd ← iv.eelse:# スキップ — 直近採用と衝突する# |result| が最大の非重複区間数
03 / このパターンを使うべき合図
「最大の非重複区間数」
教科書的なトリガー。会議室、教室予約、アクティビティ選択 —— 重ならないように最大いくつ選べるかが答えになるとき。 終点でソートして貪欲に取れば終わり。
「重複を取り除くための最少削除数」
LC 435 の言い方。同じ問題の裏返し:残せる最大 = 非重複最大、 したがって削除数 =
N − 残せる数。終点でソートする貪欲は両方を同時に与える。「最小本数のダーツで風船を割る」
LC 452。各風船は閉区間で、x に放つ矢は x を覆う全ての風船を割る。 答えは最少のグループ数 —— 反対側から数えると最大の非重複選択と等価。
「重み付き区間スケジューリング」
似て非なるもの —— 区間に重みが付き総価値の最大化が目的になると、貪欲は誤る。 この問題は終点でソートした区間上の DP となり、前駆検索を伴う(LC 1235)。
04 / よくある落とし穴
i.
終点ではなく始点でソートしてしまう。
最も多いバグ。単純な非重複入力では始点ソートでも動くが、序盤に長い区間が現れた途端に破綻する —— 採用してしまうと後ろの短い区間がまとめてブロックされる。 終点でソートすれば、局所的に最も安いコミットが大域的にも最も安全になる。
ii.
境界での厳密
> と非厳密 ≥。[1, 5] の後の [5, 8] は重なる? 閉区間(LC 452 の風船)では端点接触を 重なりとみなす —— 厳密 > を使う。 半開区間(10:00 終了の会議は 10:00 開始と衝突しない)なら ≥。 骨格は同じ、比較演算子だけが逆。iii.
「区間マージ」と混同する。
区間マージは始点でソートして重なりを 1 区間にまとめる; 区間スケジューリングは終点でソートして重ならず収まる数を数える。 見た目は似ているが、聞いていることが違う:和集合か 最大非重複部分集合か。
05 / LeetCode で練習
4 問、おおよそ難易度順。最難の LC 1235 は反例:重みが付いた途端に貪欲は崩壊し、実態は DP になる。
— / どれをいつ使うか
区間スケジューリング
入力が区間のリストで「最大いくつまで重ならないように選べるか」を問う時に使う。終点でソートし、直近に採用した終点を始点が超えている区間を順に取る。 交換論法が「最早終了」が常に安全だと保証する。
終点でソート · LC 435 · LC 452
ジャンプゲーム
各要素がそこから動ける距離を決めるときに使う。左から右へ走査し、今までに到達可能な最遠の添字を保持する。 走査位置がその境界を越えたら、終点に到達できない。
最遠を追う · LC 55 · LC 45
ガスステーション
(環状または線形の)経路で、ある累積量が常に非負でなければならないときに使う。 実行中の合計がゼロを下回った瞬間に開始位置を次へリセット — 失敗する区間は妥当な開始接頭辞にはなり得ない。
失敗で即リセット · LC 134 · LC 53