用c++完成设n个活动的集合E={1,2,3,……,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,si<fi 。如果选择了活动i,则它在半开区间[si, fi ]内占用资源。若[si, fi ]与[sj, fj ]不相交,则活动i和活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集。 输入形式为 第1行为一个整数n,n≤100,表示活动的个数。后面为n行,每行两个整数,为活动的开始时间和结束时间。 输出形式为 一个整数,表示最大的相容活动子集的元素个数。
时间: 2024-03-15 08:46:52 浏览: 161
这是一个经典的贪心算法问题,可以使用贪心算法来解决。具体思路如下:
1. 将活动按照结束时间从小到大排序。
2. 选择结束时间最早的活动,将其加入最大相容活动子集。
3. 从剩余的活动中选择开始时间大于等于已选择活动的结束时间的活动,将其加入最大相容活动子集。
4. 重复以上步骤,直到选择完所有活动。
以下是 C++ 的实现代码:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
struct Activity {
int start;
int end;
};
bool cmp(Activity a, Activity b) {
return a.end < b.end;
}
// 贪心算法求解最大相容活动子集
int max_compatible_activity_set(Activity* activities, int n) {
sort(activities, activities + n, cmp);
int count = 1;
int end_time = activities[0].end;
for (int i = 1; i < n; i++) {
if (activities[i].start >= end_time) {
count++;
end_time = activities[i].end;
}
}
return count;
}
int main() {
int n;
cin >> n;
Activity* activities = new Activity[n];
for (int i = 0; i < n; i++) {
cin >> activities[i].start >> activities[i].end;
}
cout << max_compatible_activity_set(activities, n) << endl;
delete[] activities;
return 0;
}
```
以上代码中,使用结构体 Activity 来存储每个活动的开始时间和结束时间,cmp() 函数用于按照结束时间从小到大排序,max_compatible_activity_set() 函数用于贪心求解最大相容活动子集。
时间复杂度为 O(nlogn),空间复杂度为 O(n)。
阅读全文