【C++】映画祭で参加者が最後まで観られる映画の最大本数を求めるプログラム

問題の概要

さまざまな国の映画が上映される映画祭が開催されているとしましょう。参加者は、上映時間が互いに重ならない映画をできるだけ多く観たいと考えています。そこで本記事では、参加者が最大で何本の映画を最初から最後まで観られるのかを求めるC++プログラムを紹介します。

まず、次のメンバーを持つ構造体 Movie を定義します。

• 映画の開始時刻
• 映画の上映時間（長さ）
• 映画の終了時刻

さらに、次のメンバーを持つ構造体 Festival を定義します。

• 映画祭で上映される映画の本数
• 映画の本数と同じサイズの Movie 型配列

各映画の開始時刻と上映時間をそれぞれ格納した2つの配列 timeBegin と duration を使って、Festival オブジェクトを作成・初期化します。整数 n は映画の総本数を表し、オブジェクトの初期化にも利用します。その後、このオブジェクトをもとに、参加者が全編を通して観られる映画の本数を計算します。

たとえば、timeBegin = {1, 3, 0, 5, 5, 8, 8}、duration = {3, 2, 2, 4, 3, 2, 3}、n = 7 という入力が与えられた場合、出力は 4 になります。これは、参加者がこの映画祭で合計4本の映画を最後まで観られることを意味します。

解法のアプローチ

この問題は、いわゆる「区間スケジューリング問題（活動選択問題）」の一種です。終了時刻が早い映画から順に選んでいく貪欲法（グリーディ法）を使うことで、最適解を効率よく求められます。具体的には、以下の手順で解きます。

1. 構造体 Movie を定義する
   • メンバー変数 timeBegin、duration、timeEnd の3つを宣言する
   • 比較演算子「<」をオーバーロードする。Movie 型の変数 another を引数に取り、timeEnd < another.timeEnd を返す（終了時刻の昇順でソートできるようにするため）
2. 構造体 Festival を定義する
   • メンバー count を定義する
   • Movie 型の要素を格納する配列 movies を定義する
3. 関数 initialize() を定義する（引数：配列 timeBegin、duration、整数 n）
   • filmFestival := 新しい Festival オブジェクト
   • filmFestival の count に count を代入する
   • i := 0 から i < count の間、i を1ずつ増やしながら以下を繰り返す
     • temp := 新しい Movie 型オブジェクト
     • temp の timeBegin := timeBegin[i]
     • temp の duration := duration[i]
     • temp の timeEnd := timeBegin[i] + duration[i]
     • temp を filmFestival の movies 配列に追加する
   • filmFestival を返す
4. 関数 solve() を定義する（引数：Festival 型の変数 fest）
   • res := 0
   • fest の movies 配列をソートする
   • timeEnd := -1
   • i := 0 から i < fest->count の間、i を1ずつ増やしながら以下を繰り返す
     • fest の movies[i] の timeBegin が timeEnd 以上であれば
       • res を1増やす
       • timeEnd := fest の movies[i] の timeEnd
   • res を返す

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include<bits/stdc++.h>

using namespace std;

struct Movie {
   int timeBegin, duration, timeEnd;
   bool operator<(const Movie& another) const {
      return timeEnd < another.timeEnd;
   }
};

struct Festival {
   int count;
   vector<Movie> movies;
};
Festival* initialize(int timeBegin[], int duration[], int count) {
   Festival* filmFestival = new Festival;
   filmFestival->count = count;
   for (int i = 0; i < count; i++) {
      Movie temp;
      temp.timeBegin = timeBegin[i];
      temp.duration = duration[i];
      temp.timeEnd = timeBegin[i] + duration[i];
      filmFestival->movies.push_back(temp);
   }
   return filmFestival;
}
int solve(Festival* fest) {
   int res = 0;
   sort(fest->movies.begin(), fest->movies.end());
   int timeEnd = -1;
   for (int i = 0; i < fest->count; i++) {
      if (fest->movies[i].timeBegin >= timeEnd) {
         res++;
            timeEnd = fest->movies[i].timeEnd;
      }
   }
   return res;
}

int main(int argc, char *argv[]) {
int timeBegin[] = {1, 3, 0, 5, 5, 8, 8};
int duration[] = {3, 2, 2, 4, 3, 2, 3};
Festival * fest;
fest = initialize(timeBegin,duration, 7);
cout << solve(fest) << endl;
return 0;
}

入力

int timeBegin[] = {1, 3, 0, 5, 5, 8, 8};
int duration[] = {3, 2, 2, 4, 3, 2, 3};
Festival * fest;
fest = initialize(timeBegin,duration, 7);

出力

4

まとめ

このプログラムでは、映画を終了時刻の昇順にソートし、直前に選んだ映画の終了時刻以降に始まる映画を順に選んでいくことで、観られる映画の最大本数を求めています。計算量はソート部分が支配的で O(n log n) と非常に効率的です。時間帯が重なるイベントの中から最大数を選びたい場合など、この貪欲法の考え方はさまざまなスケジューリング問題に応用できます。