C++で解く活動選択問題（貪欲法①）：アルゴリズムと実装例をわかりやすく解説

開始時刻と終了時刻が与えられた n 個の異なる活動の中から、一人の人物が時間の重複なく実行できる活動の最大数を選ぶ問題を「活動選択問題（Activity Selection Problem）」と呼びます。

本記事では、貪欲法（グリーディ法）を用いてこの問題を解く方法を解説します。貪欲法では、残りの活動の中から「終了時刻が最も早い活動」を順に選んでいきます。ただし、その活動の開始時刻は、直前に選択した活動の終了時刻以降である必要があります。

• 計算量：活動リストが未ソートの場合は O(n log n)、すでに終了時刻でソートされたリストが与えられている場合は O(n) で解けます。

活動選択問題の入力と出力

入力

各活動の開始時刻と終了時刻を含むリストを入力とします。

{(5,9), (1,2), (3,4), (0,6), (5,7), (8,9)}

出力

選択された活動は以下の通りです。

Activity: 0 , Start: 1 End: 2
Activity: 1 , Start: 3 End: 4
Activity: 3 , Start: 5 End: 7
Activity: 5 , Start: 8 End: 9

アルゴリズムの流れ

maxActivity(act, size)

入力： 活動のリストと、リスト内の要素数
出力： 選択された活動の順序

Begin
    与えられた活動リストを終了時刻の昇順にソートする
    i := 0 とする
    i 番目の活動を表示する（この場合、最初の活動）
    j := 1 から n-1 まで繰り返す
        もし act[j] の開始時刻 >= act[i] の終了時刻 ならば
            j 番目の活動を表示する
            i := j とする
    繰り返し終了
End

なぜ「終了時刻が最も早い活動」を選ぶことが有効なのでしょうか。それは、早く終わる活動を選ぶほど、その後に使える時間が長く残り、結果として選べる活動の総数が最大になる可能性が高まるからです。これこそが貪欲法の基本的な考え方です。

C++による実装例

#include <iostream>
#include <algorithm>
using namespace std;

struct Activity {
    int start, end;
};

// 終了時刻の昇順で比較する関数
bool comp(Activity act1, Activity act2) {
    return (act1.end < act2.end);
}

void maxActivity(Activity act[], int n) {
    sort(act, act + n, comp); // 比較関数を使って活動をソート
    cout << "Selected Activities are: " << endl;
    int i = 0; // 最初の活動（インデックス0）を選択
    cout << "Activity: " << i << " , Start: " << act[i].start << " End: " << act[i].end << endl;
    for (int j = 1; j < n; j++) { // 残りのすべての活動を確認
        if (act[j].start >= act[i].end) { // 開始時刻が前の活動の終了時刻以降なら採用
            cout << "Activity: " << j << " , Start: " << act[j].start << " End: " << act[j].end << endl;
            i = j;
        }
    }
}

int main() {
    Activity actArr[] = {{5,9},{1,2},{3,4},{0,6},{5,7},{8,9}};
    int n = 6;
    maxActivity(actArr, n);
    return 0;
}

実行結果

Selected Activities are:
Activity: 0 , Start: 1 End: 2
Activity: 1 , Start: 3 End: 4
Activity: 3 , Start: 5 End: 7
Activity: 5 , Start: 8 End: 9

まとめ

活動選択問題は、貪欲法を適用できる典型的な例題です。終了時刻の早い活動から順に選ぶことで、一人の人物が実行できる活動数を最大化できます。計算量はリストがソート済みなら O(n)、未ソートなら O(n log n) と非常に効率的であり、スケジューリングやリソース割り当てなどの実務上の問題にも応用できる重要な考え方です。