C++ 程序用于找出电影节参与者可以完整观看多少部电影
c++server side programmingprogramming
假设正在举办一个电影节，展示来自不同国家的各种电影。现在，一位参与者想要观看不相互重叠的最大数量的电影，我们必须帮助他们找出他们可以观看多少部电影。
有一个结构 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 类型变量 another。
- 返回 timeEnd < another.timeEnd
- struct Festival {
- 定义成员计数
- 定义包含 Movie 类型项目的数组 movies
- 定义一个函数initialize()。这将采用数组timeBegin和timeEnd以及一个iteger 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中
- return filmFestival
- 定义一个函数solve()，它将接受一个Fest类型的变量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
- 如果fest的movies[i]的timeBegin >= timeEnd，则−
- 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
