貪欲法
01 / 共通の仕組み
各ステップで局所最適を確定し、その確定が後で覆らないことを示す。 バックトラックも DP テーブルも要らない:交換論法でどの貪欲な選択を入れ替えても 改善できないと示すか、先行論法で貪欲がどの接頭辞でも遅れないと示す。 この発想を 3 つの古典的サブパターンに落とし込む: 区間でソートして取る、配列上で到達範囲を追う、累積量で「失敗したらリセット」。
上から一つのサブパターンを選んでください。それぞれ単独でリンクできます — 問題に一番近いものから始めましょう。
↑ 選ぶ— / どれをいつ使うか
区間スケジューリング
入力が区間のリストで「最大いくつまで重ならないように選べるか」を問う時に使う。終点でソートし、直近に採用した終点を始点が超えている区間を順に取る。 交換論法が「最早終了」が常に安全だと保証する。
終点でソート · LC 435 · LC 452
ジャンプゲーム
各要素がそこから動ける距離を決めるときに使う。左から右へ走査し、今までに到達可能な最遠の添字を保持する。 走査位置がその境界を越えたら、終点に到達できない。
最遠を追う · LC 55 · LC 45
ガスステーション
(環状または線形の)経路で、ある累積量が常に非負でなければならないときに使う。 実行中の合計がゼロを下回った瞬間に開始位置を次へリセット — 失敗する区間は妥当な開始接頭辞にはなり得ない。
失敗で即リセット · LC 134 · LC 53