【Python】アクティビティ選択問題を貪欲法で解く方法をわかりやすく解説

この記事では、以下の問題文に対する解決策について詳しく解説していきます。

問題文

問題： n個のアクティビティと、それぞれの開始時刻および終了時刻が与えられます。1人が同時に1つのアクティビティしか実行できないという条件のもと、実行できるアクティビティの最大数を選択してください。

変数の定義

• N ― アクティビティの総数
• S ― すべてのアクティビティの開始時刻を格納する配列
• F ― すべてのアクティビティの終了時刻を格納する配列

アルゴリズムの考え方：貪欲法（グリーディ法）

この問題は貪欲法を用いることで効率的に解くことができます。基本的な戦略は次のとおりです。

1. アクティビティを終了時刻の早い順に並べ替えます。
2. 最初に終わるアクティビティを必ず選択します。これにより、残りに使える時間が最も長くなります。
3. 以降のアクティビティの中から、「直前に選んだアクティビティの終了時刻以降に開始するもの」を順に選んでいきます。

終了時刻の早いアクティビティから優先的に選ぶことで、後続のアクティビティにできるだけ多くの時間を残せます。その結果、選択できるアクティビティの総数が最大化されます。

実装例

# 1人が実行できるアクティビティの最大数を求める
def Activities(s, f):
    n = len(f)
    print("選択されたアクティビティ:")
    # 最初のアクティビティは必ず選択される
    i = 0
    print(i, end=" ")
    # 残りのアクティビティを順に確認
    for j in range(n):
        # 開始時刻が、直前に選んだアクティビティの終了時刻以上の場合
        if s[j] >= f[i]:
            print(j, end=" ")
            i = j

# メイン処理
s = [1, 2, 0, 3, 2, 4]
f = [2, 5, 4, 6, 8, 8]
Activities(s, f)

出力

選択されたアクティビティ:
0 1

上記の例では、インデックス0（開始時刻1・終了時刻2）とインデックス1（開始時刻2・終了時刻5）の2つのアクティビティが選択されています。すべての変数はローカルスコープ内で宣言されており、その参照関係は下図のとおりです。

計算量

アクティビティがすでに終了時刻の昇順に並んでいる場合は、配列を一度走査するだけでよいため、時間計算量は O(n) となります。ソートが必要なケースでは、全体の計算量は O(n log n) になります。

まとめ

この記事では、貪欲法を用いてアクティビティ選択問題を解くPythonプログラムの作成方法を学びました。「終了時刻の早いアクティビティから順に選んでいく」というシンプルな戦略こそが、最適解を導く鍵となります。スケジューリングやリソース割り当てなど、実務のさまざまな場面にも応用できる考え方なので、ぜひマスターしておきましょう。