見出し画像

貪欲法：区間スケジューリング問題

堀川圭一

この記事は、chatGPTが書いています。
貪欲法の2回目です。
リンク先のnotebookで動作確認できます。ぜひ、動かしてみてください。


【貪欲法解説記事・第2回】区間スケジューリング問題をPythonで解いてみよう！

みなさん、こんにちは！
前回（第1回）では、コイン問題を題材に、貪欲法（Greedy Algorithm）の基本的な考え方を学びました。
今回は、貪欲法の定番例として有名な 「区間スケジューリング問題」 を、Pythonを使って一緒に解いてみましょう。

1. 区間スケジューリング問題とは？

「区間スケジューリング問題」は、ざっくり言うと

「複数のイベント（開始時刻・終了時刻）がある中で、重ならないように、できるだけ多くのイベントを選びたい！」

という状況を考える問題です。たとえば、会議室が1つしかないのに、会議をなるべく多く実施したい場合や、大学の教室でできるだけ多くの授業を組みたい場合など、“現実でもよくあるシチュエーション” と言えます。

例：

  • イベントA：9時開始、10時終了

  • イベントB：9時半開始、11時終了

  • イベントC：10時開始、10時半終了

  • … などなど

これを「どの順番で組んでいくと、全部で何個のイベントを開催できるか？」と悩むわけです。
今回のコードでは「開始時刻」と「終了時刻」のタプルを並べて、重ならないように取れる最大の区間数を計算します。

2. 貪欲法の戦略：なぜ「終了時刻が早い」順？

区間スケジューリング問題を貪欲法で解く際には

「終了時刻が早い順」 に区間を並べ、順に 「まだ使える（重ならない）区間」 をどんどん選んでいく。

という方法がよく使われます。
なぜ終了時刻の早い順でソートするとうまくいくのか？
カンタンに言えば、後に控えているイベントの“受け入れ余地”をなるべく広くするためです。
「早く終わるイベント」を優先的に採用するほうが、残りの時間帯に別のイベントを詰め込みやすいわけですね。

ワンポイント：ほかの並べ方（開始時刻が早い順や区間の短さ順など）では、最適解を逃す可能性があります。 一方、終了時刻の早い順で選んでいく方法は、数学的にも「常に最適解を導くことができる」と証明されています。

3. Pythonコードで実装する

以下が、区間スケジューリング問題を貪欲法で解くサンプルコードです。
コメントも丁寧につけていますので、ぜひ読み進めながら流れを理解してください。

def interval_scheduling(intervals):
    """
    貪欲法を使用して、選べる最大の区間数を求める関数。

    Args:
        intervals (list of tuple): 各区間の開始時刻と終了時刻を表すタプルのリスト。
                                   例) [(start1, end1), (start2, end2), ...]

    Returns:
        int: 選べる最大の区間数。
    """
    # 1. 終了時刻が早い順にソート
    intervals.sort(key=lambda x: x[1])

    # 2. 選択した区間の数と、現在の終了時刻を管理する変数
    max_intervals = 0
    current_end_time = 0

    # 3. ソート済みの区間を順番に確認
    for start, end in intervals:
        # 4. 区間が重ならない（開始 >= 現在の終了時刻）場合は採用する
        if start >= current_end_time:
            max_intervals += 1      # 区間を1つ追加
            current_end_time = end  # 終了時刻を更新

    # 5. 選べた区間の最大数を返す
    return max_intervals

# --- 動作確認用のコード ---
if __name__ == "__main__":
    # サンプルの区間データ（開始時刻, 終了時刻）
    intervals = [
        (1, 3),
        (2, 5),
        (3, 9),
        (6, 8),
        (4, 6)
    ]

    # 関数を呼び出して結果を確認
    result = interval_scheduling(intervals)
    print(f"選べる最大の区間数: {result}")

4. コードの流れをじっくり解説

4-1. intervals.sort(key=lambda x: x[1])

  • intervals は (開始時刻, 終了時刻) のタプルを要素に持つリストです。

  • key=lambda x: x[1] とすることで、タプルの 終了時刻 を使ってソートします。

  • ソートが終わると、intervals は「終了時刻が小さい順」に並びます。

4-2. max_intervals と current_end_time

  • max_intervals: 選択した区間の合計数をカウントします。初めは0。

  • current_end_time: 直前に選んだ区間の終了時刻を記録します。最初は何も選んでいないので0と設定しています（問題次第では別の値を入れるケースも）。

4-3. for start, end in intervals:

  • ソート済みの区間をひとつずつチェックしていきます。

4-4. if start >= current_end_time:

  • 区間が重ならないかを調べます。

  • 「新しい区間の開始時刻 (start) が、前の区間の終了時刻 (current_end_time) より後」であれば衝突しません。

  • 衝突しなければ、

    • max_intervals += 1 で採用する。

    • current_end_time = end で終了時刻を更新しておきます。

4-5. return max_intervals

  • 最終的に採用できた区間の数を返して終わり。

5. 動作イメージ：サンプルの区間を並べ替えてみる

たとえば下記の区間リストを見てみましょう。

intervals = [
    (1, 3),  # A
    (2, 5),  # B
    (3, 9),  # C
    (6, 8),  # D
    (4, 6)   # E
]

  1. 終了時刻順にソートすると、終了時刻が

    • A:3, B:5, E:6, D:8, C:9となるので、ソート後のリストは [(1,3), (2,5), (4,6), (6,8), (3,9)] になります。

  2. 順に確認すると、

    • (1,3) → 開始1 >= 0 (current_end_time=0) なのでOK

      • 選択 → max_intervals=1, current_end_time=3

    • (2,5) → 開始2 < current_end_time(3) なので重複 → スキップ

    • (4,6) → 開始4 >= 3 → OK → max_intervals=2, current_end_time=6

    • (6,8) → 開始6 >= 6 → OK → max_intervals=3, current_end_time=8

    • (3,9) → 開始3 < current_end_time(8) なので重複 → スキップ

    • 結果：最大3つの区間を取れる。

こうして区間の情報を整理すると、「早く終わる区間から順に採用する」貪欲法のメリットが実感できます。

6. 貪欲法は本当に万能？

貪欲法は、今回のように最適解を導くケースが多数存在します。一方で、必ずしもどんな問題でも成功するわけではありません。
問題によっては、動的計画法（Dynamic Programming） など、もっと複雑な手法が必要になるケースもあります。
しかし、区間スケジューリングのように「終了時刻でソートするだけ」で解ける」問題は、学習者にとって貪欲法のシンプルかつ強力な魅力を体験するのにうってつけです。

7. まとめ & 次回予告

  • 今回は、区間スケジューリング問題で貪欲法を使う方法を学びました。

  • 終了時刻の早い順にソートし、前の区間と重ならない場合は選ぶ――この単純な戦略で、驚くほどサクッと最適解を得られます。

  • コードも ソート + 1つのループ という、とてもシンプルな構造でしたね。

次回（第3回）は、さらにユニークな 「multiple array の問題」 を扱います。

  • これは、2つの数列 A, B が与えられ、A の各要素が B の各要素の倍数になるよう、A に+1する操作を行うには、どんな順番で何回押せばいいか？―― という問題です。

  • 果たして貪欲法が役立つのか？ それとも別のアプローチが必要か？ 次回もお楽しみに！

ぜひ実行してみてください！

初心者の方は、まずは上記のコードをコピーして自分の環境で動かしてみてください。

  • コードを少し改造してみる（区間を変える・多くする）だけでも、理解がさらに深まります。

  • 経験者の方も、改めて貪欲法の基礎を振り返るきっかけとしてお役立てください。

それではまた次回、アルゴリズムの世界を楽しんでいきましょう。

補足：print文で実行過程を可視化

こちらも、notebookにありますので、動かしてみたください。

def interval_scheduling(intervals):
    """
    貪欲法を使用して選べる最大の区間数を求める関数。
    処理過程をわかりやすくするため、print文を入れて動作を確認できるようにしています。
    """

    print("=== 処理開始 ===")
    print(f"ソート前の区間リスト: {intervals}")

    # 1. 終了時刻が早い順にソート
    intervals.sort(key=lambda x: x[1])
    print(f"ソート後の区間リスト(終了時刻基準): {intervals}\\n")

    # 2. 選んだ区間の数と、現在の終了時刻を管理
    max_intervals = 0
    current_end_time = 0

    # 3. ソートされた区間を順にチェック
    for start, end in intervals:
        print(f"検討中: 開始={start}, 終了={end}")
        # 4. 前の区間と重ならない場合のみ採用
        if start >= current_end_time:
            print("  → 採用します。")
            max_intervals += 1
            current_end_time = end
        else:
            print("  → 重なるためスキップ。")

        print(f"  現在の選択数: {max_intervals}, 直近の終了時刻: {current_end_time}\\n")

    print("=== 処理終了 ===")
    print(f"最終的に選べる区間数: {max_intervals}\\n")

    return max_intervals

# --- 最小限の動作確認用コード ---
if __name__ == "__main__":
    # サンプルの区間データ（開始時刻, 終了時刻）
    intervals = [
        (1, 3),
        (2, 5),
        (3, 9),
        (6, 8),
        (4, 6)
    ]
    result = interval_scheduling(intervals)
    print(f"結果: {result}")

最小限の解説:

  1. ソート前後のリストを print して、終了時刻に基づく並び替えが確認できます。

  2. 各区間を順番に見て、「重ならなければ採用」とし、max_intervals と current_end_time を更新します。

  3. スキップした区間と採用した区間を明示的に出力しているため、動作の流れが直感的に把握できます。

いいなと思ったら応援しよう！