活動選択問題をC言語で解く方法｜貪欲法による実装をわかりやすく解説

活動選択問題（Activity Selection Problem）とは、開始時刻と終了時刻が与えられた複数の活動の中から、「同時に実行できる活動は1つだけ」という条件のもとで、実行可能な活動の最大数を見つける問題です。

この問題では、次に実行すべき活動を選択する際に貪欲法（グリーディアルゴリズム）が用いられます。まずは、貪欲法の基本的な仕組みから確認していきましょう。

貪欲法（Greedy Algorithm）とは

貪欲法とは、問題の解を一歩ずつ積み重ねて構築していくアルゴリズムです。各ステップで次の一手を選ぶとき、その時点で最も有望と考えられる選択、すなわち他の選択肢よりも即座に良い結果をもたらし、最適解へ近づけるものを採用します。中間的な各ステップで最適な選択を積み上げることで、問題全体の最適解の導出を目指すため、貪欲法は最適化問題の解法として広く活用されています。

ただし、貪欲法は万能ではなく、すべての問題に適用できるわけではありません。例えば、0-1ナップサック問題は貪欲法では解くことができません。

貪欲法が用いられる代表的なアルゴリズム

貪欲法を採用している標準的なアルゴリズムには、以下のようなものがあります。

1) ダイクストラ法（最短経路問題）
2) 最小全域木（MST）{プリム法・クラスカル法}
3) ハフマン符号化

活動選択問題へのアプローチ

活動選択問題では、開始時刻と終了時刻を持つn個の活動が与えられます。そのうえで、「ある時点で実行できるのは1つの活動だけ」という条件のもと、1人の人物が実行できる活動の数を最大化することを目指します。

ここで、終了時刻の昇順に並べ替えた3つの活動を例に考えてみましょう。

Start = [1 , 5 , 12]
End   = [10, 13, 23]

この場合、実行できる活動は最大で2つです。選択されるのはインデックス[0, 2]の2つの活動です。活動0（時刻1〜10）の終了後、活動1（時刻5〜13）は開始時刻が前の活動の終了時刻より早いため選択できませんが、活動2（時刻12〜23）は開始時刻12が活動0の終了時刻10以降であるため実行可能です。

C言語での実装例

以下は、活動選択問題を貪欲法で解くCプログラムです。終了時刻でソート済みの配列に対して、最初の活動を必ず選び、その後は「直前に選んだ活動の終了時刻以降に開始する活動」を順番に選んでいくのがポイントです。

#include<stdio.h>
int main(){
    int start[] = {1 , 5 , 12};
    int finish[] = {10, 13, 23};
    int activities = sizeof(start)/sizeof(start[0]);
    int i, j;
    printf ("Following activities are selected \t");
    i = 0;
    printf("%d\t", i);
    for (j = 1; j < activities; j++){
        if (start[j] >= finish[i]){
            printf ("%d ", j);
            i = j;
        }
    }
    return 0;
}

実行結果

Following activities are selected 0 2