设有n个活动的集合E={1,2,...,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间s_i和一个结束时间f_i,且s_i Input 第一行一个整数n; 接下来的n行,每行两个整数s_i和f_i。 Output 输出互相兼容的最大活动个数。 Sample Input 4 1 3 4 6 2 5 1 7 Sample Output 2 C++scanf函数实现,并且给我具体代码
时间: 2024-02-05 08:13:35 浏览: 31
这是一个经典的贪心算法问题,可以按照结束时间从早到晚排序,每次选择结束时间最早且与前面的活动不冲突的活动。
C++代码如下:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
struct Activity {
int start; // 起始时间
int end; // 结束时间
} act[MAXN];
bool cmp(Activity a, Activity b) {
return a.end < b.end; // 按照结束时间从早到晚排序
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> act[i].start >> act[i].end;
}
sort(act, act + n, cmp); // 排序
int cnt = 1; // 记录互相兼容的活动个数,初始值为1
int end_time = act[0].end; // 记录最近结束时间,初始值为第一个活动的结束时间
for (int i = 1; i < n; i++) {
if (act[i].start >= end_time) { // 如果当前活动的起始时间晚于等于最近结束时间,说明不冲突
cnt++;
end_time = act[i].end; // 更新最近结束时间
}
}
cout << cnt << endl;
return 0;
}
```