C++ program to calculate how many movies at a film festival participants can watch in full

Suppose there is a film festival that showcases various films from different countries. Now, a participant wants to attend as many non-overlapping movies as possible, and we need to help them figure out how many movies they can attend.

There is a structure Movie, which has the following members:

• The starting time of the movie.
• The duration of the movie.
• The end time of the movie.

There is also a structure Festival, which has the following members:

• The number of films in the festival.
• An array of type Movie whose size is the same as the number of movies in the festival.

We need to create and initialize a Festival object, which contains two arrays 'timeBegin' and 'duration', which contain the start time and duration of multiple movies respectively. The integer n represents the total number of movies and is also used to initialize the object. We further use this object to calculate how many movies a participant can watch in full.

So if the input is timeBegin = {1, 3, 0, 5, 5, 8, 8}, duration = {3, 2, 2, 4, 3, 2, 3}, n = 7 , then the output will be 4

Participants can watch 4 movies in full at the festival.

In order to solve this problem, we will follow the following steps:

• Structure Movie {
  • Define three member variables timeBegin, duration, timeEnd
  • Overloaded operator '
  • Return timeEnd

Structure Festival {

• Define a member variable count
• Define an array containing Movie type items movies

Define a function initialize(), which will accept the arrays timeBegin and timeEnd and an integer n.

• filmFestival := a new Festival object
• filmFestival’s count := count
• For initialization i := 0, when i
• temp := timeBegin of a new Movie type object
• temp := timeBegin[i]
• temp duration := duration[ i]
• timeEnd of temp := timeBegin[i] duration[i]
• Insert temp into the movies array of filmFestival

Return to filmFestival

Define a function solve(), which will accept a variable fest of type Festival,

• res := 0
• Movies for fest The array is sorted
• timeEnd := -1
• For initialization i := 0, when i count, update (increase i by 1), perform the following operations:
  • If timeBegin of fest's movies[i] >= timeEnd, perform the following operations:
    • (Increase res by 1)
    • timeEnd := timeEnd of fest's movies[i]
• Return res

Example

Let us look at the following implementation to better Well understood:

#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;
}

input

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);

output

4

The above is the detailed content of C++ program to calculate how many movies at a film festival participants can watch in full. For more information, please follow other related articles on the PHP Chinese website!