活動選択問題（Activity Selection Problem）とは？貪欲法による解き方をC++実装付きで解説

活動選択問題（Activity Selection Problem）は、開始時刻と終了時刻を持つ n 個の異なる活動が与えられ、その中から一人の人間が時間の重複なく実行できる活動の最大数を選択する古典的なアルゴリズム問題です。

この問題は貪欲法（グリーディ法）を用いて解くのが一般的です。基本的な考え方は、「残りの活動の中で最も早く終わる活動」を順に着目し、その開始時刻が「直前に選択した活動の終了時刻」以降であれば採用する、というものです。終了時刻の早い活動から優先的に選ぶことで、後続の活動に使える時間を最大化できます。

計算量

• 活動リストがソートされていない場合：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

この例では、元のリストを終了時刻の昇順に並べ替えた上で選択を行うため、(1,2)、(3,4)、(5,7)、(8,9) の4つの活動が採用されます。(0,6) や (5,9) のように他の活動と時間帯が重なる活動は除外されます。

アルゴリズム

maxActivity(act, size)

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

Begin
    与えられた活動リストを最初にソートする
    i := 1 とする
    i番目の活動を表示する // この場合、最初の活動

    for j := 1 to n-1 do
        if act[j] の開始時刻 >= act[i] の終了時刻 then
            j番目の活動を表示する
            i := j
    done
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 log n)、ソート済みなら O(n) と効率的であり、会議室の割り当てやタスクスケジューリングなど、実務上のスケジュール最適化にも応用できる考え方です。