A18788. 校园活动安排
填空题
较难
知识点
题目描述
校园活动安排
题目描述
学校有n个社团活动，每个活动有开始时间l[i]和结束时间r[i]。
同一时间只能参加一个活动，活动结束瞬间可以参加下一个活动。
求最多能参加多少个活动。
输入格式
第一行一个整数n；接下来n行，每行两个整数l,r，表示活动的起止时间。
输出格式
输出一个整数，表示最多可参加的活动数量。
数据范围 1≤n≤2000
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
struct Node
{
int l, r; // l开始时间，r结束时间
}act[2005];
// 核心：按结束时间升序排序
bool cmp(Node a, Node b)
{
return a.r < b.r;
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> act[i].l >> act[i].r;
}
sort(act, act + n, cmp);
int cnt = 0;
int last_end = -1; // 记录上一个活动的结束时间
for(int i = 0; i < n; i++)
{
if(act[i].l >= last_end) // 满足接续条件
{
cnt++;
last_end = act[i].r;
}
}
cout << cnt;
return 0;
}答案解析
1. 核心考点：经典最多不重叠区间模板；
2. 排序规则：按结束时间（右端点）升序，优先选结束早的活动，预留最多后续时间；
3. 遍历规则：当前活动开始时间 ≥ 上一个活动结束时间，则可选，更新结束时间；
4. 关键坑点：判断条件必须用>=，满足“结束瞬间可接续”的题目要求。
评分细则
结构体定义正确（3分）、cmp按右端点排序正确（8分，写左端点直接扣8分）、遍历判断条件正确（8分）、输入输出规范（4分）、无bug（2分）
上一题
下一题