用c++求解输入描述:第一行是一个整数n(≤10000),接着n行中每一行包括两个整数b和e (1 ≤ b ≤ e ≤ 300000),其中b是活动开始时间,e是活动结束时间。 • 输出描述:输出所有活动占用时间的最大值
时间: 2024-02-25 15:55:32 浏览: 72
好的,这是一个经典的贪心问题,可以使用C++来求解。下面是一个可能的实现,供参考:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Activity {
int begin;
int end;
};
bool cmp(Activity a, Activity b) {
return a.end < b.end;
}
int main() {
int n;
cin >> n;
vector<Activity> activities(n);
for (int i = 0; i < n; i++) {
cin >> activities[i].begin >> activities[i].end;
}
sort(activities.begin(), activities.end(), cmp);
int end_time = 0;
int max_duration = 0;
for (int i = 0; i < n; i++) {
if (activities[i].begin >= end_time) {
int duration = activities[i].end - activities[i].begin;
if (duration > max_duration) {
max_duration = duration;
}
end_time = activities[i].end;
}
}
cout << max_duration << endl;
return 0;
}
```
这段代码的基本思路是,首先按照活动的结束时间从小到大排序,然后依次遍历每个活动,如果当前活动的开始时间晚于等于上一个活动的结束时间,说明它可以被安排在上一个活动之后,此时计算它的持续时间,并更新最大持续时间;如果当前活动的开始时间早于上一个活动的结束时间,说明它与上一个活动有冲突,应该跳过。最后输出最大持续时间即可。
阅读全文