C++程式：計算參加電影節的觀眾可以完整觀看的電影數量

假設正在舉辦一個電影節，展映來自不同國家的各種電影。現在，一位參加者希望參加儘可能多的不重疊的電影，我們需要幫助他們找出可以參加的電影數量。

有一個名為Movie的結構體，包含以下成員：

  • 電影的開始時間。
  • 電影的時長。
  • 電影的結束時間。

還有一個名為Festival的結構體，包含以下成員：

  • 電影節上電影的數量。
  • 一個型別為Movie的陣列，其大小與電影節上電影的數量相同。

我們需要建立一個Festival物件，並使用兩個陣列'timeBegin'和'duration'分別初始化電影的開始時間和時長。整數n表示電影的總數，也用於初始化物件。我們進一步利用該物件來計算參加者可以完整觀看的電影數量。

因此，如果輸入類似於timeBegin = {1, 3, 0, 5, 5, 8, 8}，duration = {3, 2, 2, 4, 3, 2, 3}，n = 7，則輸出將為4。

參加者可以在該電影節上完整觀看總共4部電影。

為了解決這個問題，我們將遵循以下步驟：

  • struct Movie {
    • 定義三個成員變數timeBegin、duration、timeEnd
    • 過載運算子‘<’，它將接收一個Movie型別的變數和另一個。
      • 返回timeEnd < another.timeEnd
  • struct Festival {
    • 定義一個成員count
    • 定義一個包含Movie型別項的陣列movies
  • 定義一個函式initialize()。它將接收陣列timeBegin和timeEnd以及一個整數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
  • 定義一個函式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

示例

讓我們看看以下實現以更好地理解：

#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

更新於： 2021年10月20日

372 次瀏覽

開啟您的 職業生涯

完成課程並獲得認證

立即開始
廣告