参加者が映画祭で完全に見ることができる映画の数を調べるためのC++プログラム

さまざまな国のさまざまな映画を紹介する映画祭が開催されているとします。現在、参加者は互いに重複しない最大数の映画に参加したいと考えており、参加できる映画の数を見つけるのを支援する必要があります。

次のメンバーを持つ構造ムービーがあります-

• 映画の開始時間。
• 映画の長さ。
• 映画の終了時間。

次のメンバーで構成される別の構造フェスティバルがあります-

• 映画祭での映画の数。
• 映画祭の映画の数と同じサイズの映画タイプの配列。

複数の映画の開始時間と長さをそれぞれ含む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本の映画を完全に見ることができます。

これを解決するには、次の手順に従います-

• struct Movie {
  • 3つのメンバー変数timeBegin、duration、timeEndを定義します
  • 演算子「<」をオーバーロードします。これにより、Movie型変数が別の変数になります。
    • return timeEnd
• struct Festival {
  • 会員数を定義する
  • Movieタイプのアイテムを含む配列ムービーを定義します
• 関数initialize（）を定義します。これには、配列timeBeginとtimeEnd、およびitegernが必要です。
  • filmFestival：=新しいフェスティバルオブジェクト
  • filmFestivalのカウント：=カウント
  • iを初期化する場合：=0、i <カウント、更新（iを1増やす）の場合、-
    を実行します。
    • temp：=Movieタイプの新しいオブジェクト
    • timeBegin of temp：=timeBegin [i]
    • tempの期間：=duration [i]
    • timeEnd of temp：=timeBegin [i] + duration [i]
    • filmFestivalのアレイムービーに臨時雇用者を挿入
  • 映画祭を返す
• 関数solve（）を定義します。これにより、Festival型の可変フェストが発生します。
  • res：=0
  • フェストの一連の映画を並べ替える
  • timeEnd：=-1
  • iを初期化する場合：=0、i count、update（iを1増やす）の場合、-
    を実行します。
    • 映画のtimeBegin[i]of fest> =timeEndの場合、-
      • （解像度を1増やします）
      • timeEnd：=映画のtimeEnd [i] of fest
  • return res

例

理解を深めるために、次の実装を見てみましょう-

#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