貪欲法 — 「目先のベスト」を選び続けてよい問題の見極め

貪欲法（greedy）は、「その場その場で一番良さそうな選択をし続ける」解法です。全探索が2^N通りを試すところを、貪欲法は1本道しか通りません。だからO(N log N)程度で終わり、実装も短い——ハマれば最強の解法です。

ただし貪欲法には重大な注意があります。正しいときと正しくないときがあるのです。この章の目標は、書けるようになること以上に、「貪欲でいけるか」を見極められるようになることです。

代表例: 区間スケジューリング問題

貪欲法の教科書的名作からいきます。paiza・AtCoder・面接の全戦場で出会う問題です。

問題: N件の仕事があり、それぞれ開始時刻と終了時刻を持つ。時間が重ならないように選ぶとき、最大で何件の仕事を選べるか。（N ≤ 10^5）

全探索は2^N通りで論外。ここで貪欲法の出番です。戦略はこうです。

終了時刻が最も早い仕事から順に、選べるなら選ぶ。

function maxJobs(jobs: [number, number][]): number {
  // 終了時刻でソート（第8章: ソートは前処理）
  jobs.sort((a, b) => a[1] - b[1]);
 
  let count = 0;
  let lastEnd = -Infinity;
  for (const [start, end] of jobs) {
    if (start >= lastEnd) {   // 前に選んだ仕事と重ならないなら
      count++;                // 選ぶ
      lastEnd = end;
    }
  }
  return count;
}

O(N log N)。たったこれだけで最適解が出ます。

学習者

待って、なんで「終了が早い順」なの？「開始が早い順」とか「時間が短い順」じゃダメなの？

最高の質問です。実は「開始が早い順」も「短い順」も間違いで、反例が作れます。

開始が早い順の反例:
  仕事A: [1, 100]  ← 開始最速だが、これを選ぶと他が全滅
  仕事B: [2, 3]、仕事C: [4, 5]  ← 本当はこの2つを選ぶべき

短い順の反例:
  仕事A: [4, 6]（長さ2で最短） ← これを選ぶと…
  仕事B: [1, 5]、仕事C: [5, 9]  ← 両方潰れる。B+Cの2件が正解

「終了が早い順」だけが正しい理由は、直感的には「早く終わる仕事は、残り時間を最大限残してくれる」からです。終了最速の仕事を選ばない最適解があったとしても、その最初の仕事を終了最速のものに置き換えても損しない——という交換しても悪化しない論法で正当性が保証できます。

貪欲法が成立する条件

区間スケジューリングの例から、一般則を抽出します。貪欲法が正しいのは、次の性質があるときです。

いま最善に見える選択が、将来の選択肢を（他のどの選択と比べても）狭めない。

これを確かめる実戦的な方法が2つあります。

1. 交換論法 — 「最適解の選択を貪欲の選択に置き換えても悪化しないか？」を考える
2. 小さい反例探し — 要素2〜3個の意地悪なケースを自作して、貪欲の答えと全探索の答えを比べる

テスト本番では厳密な証明は不要です。しかし反例探しを30秒やるだけで、「貪欲で突っ込んで撃沈」がかなり防げます。

頻出の貪欲パターン

区間スケジューリング以外の定番も、駆け足で見ておきます。

おつりの硬貨枚数（500円・100円・50円…）

大きい硬貨から使えるだけ使う——日本の硬貨系（各額面が倍数関係に近い）では貪欲が最適です。ただし額面が 1, 3, 4 のような一般のコインでは貪欲は最適とは限りません（6円 = 3+3が最適だが、貪欲は4+1+1）。これは次章DPの担当です。

出発が早い順に割り当てる(マッチング系)

「客に部屋を割り当てる」「タスクを担当者に振る」系は、締切や開始時刻でソートして順に割り当てる貪欲が定番です。

ペア作りは「大きい+小さい」

「合計がK以下のペアを最大数作る」系は、ソートして最大と最小をぶつける二つのポインタ（第3章）+ 貪欲の合わせ技になります。

共通するのは、**すべて「ソートしてから1周」**という形です。「何順に並べれば1本道で決めてよくなるか？」がこの解法の設計ポイントだと分かります。

貪欲で解けない問題を見抜く

貪欲法の学習は「使わない判断」とセットで完成します。シグナルはこれです。

メンター

迷ったときの判断はシンプルです。貪欲は「クビにしやすい仮説」——実装が数分で終わるので、まず反例を探し、見つからなければ書いて提出してみる。落ちたらDPに切り替える。この損切りの早さも実戦力のうちですよ。

この章のパターンの見分け方

まとめ

• 貪欲法 = 「その場のベストを選び続ける」1本道の解法。ほぼ常にソートとセット
• 区間スケジューリングは「終了時刻が早い順」。開始順・短い順は反例あり
• 正当性の確認は「交換して悪化しないか」+「小さい反例を30秒探す」
• ナップサック型・一般コイン・数え上げは貪欲の敗北パターン。DPへ切り替える
• 実装が軽いので「仮説として試し、ダメなら損切り」も実戦では有効

次章は、貪欲法が敗れる問題を引き受ける本丸——動的計画法（DP）です。「表を埋める」という一つのイメージで、ナップサックから経路数まで攻略します。