csp信奥赛C++高频考点专项训练之贪心算法 --【区间贪心】：线段覆盖
题目描述
现在各大 oj 上有n nn个比赛，每个比赛的开始、结束的时间点是知道的。
yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。
所以，他想知道他最多能参加几个比赛。
由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加2 22个及以上的比赛。
输入格式
第一行是一个整数n nn，接下来n nn行每行是2 22个整数a i , b i ( a i < b i ) a_{i},b_{i}\ (a_{i}<b_{i})ai,bi(ai<bi)，表示比赛开始、结束的时间。
输出格式
一个整数最多参加的比赛数目。
输入输出样例 1
输入 1
3 0 2 2 4 1 3输出 1
2说明/提示
- 对于20 % 20\%20%的数据，n ≤ 10 n \le 10n≤10；
- 对于50 % 50\%50%的数据，n ≤ 10 3 n \le 10^3n≤103；
- 对于70 % 70\%70%的数据，n ≤ 10 5 n \le 10^{5}n≤105；
- 对于100 % 100\%100%的数据，1 ≤ n ≤ 10 6 1\le n \le 10^{6}1≤n≤106，0 ≤ a i < b i ≤ 10 6 0 \le a_{i} < b_{i} \le 10^60≤ai<bi≤106。
AC代码
#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;// 定义最大数据范围// 定义活动结构体，s为开始时间，e为结束时间structnode{ints,e;}a[N];// 自定义排序规则，按结束时间升序排列boolcmp(node x,node y){returnx.e<y.e;}intmain(){intn;cin>>n;// 读入所有活动的开始和结束时间for(inti=1;i<=n;i++){cin>>a[i].s>>a[i].e;}// 按结束时间升序排序，便于贪心选择sort(a+1,a+n+1,cmp);intans=1;// 至少可以参加第一个活动intnow=1;// 当前最后参加的活动是第一个// 从第二个活动开始遍历for(inti=2;i<=n;i++){// 如果当前活动的开始时间 >= 已选活动的结束时间，则选择该活动if(a[i].s>=a[now].e){ans++;now=i;// 更新最后参加的活动为当前活动}}cout<<ans;return0;}功能分析
该程序解决了活动选择问题，目标是找出不重叠的最大活动数量。采用贪心算法策略：
排序阶段：将所有活动按结束时间升序排序。这样每次可以优先选择结束时间最早的活动，为后续活动留出更多时间。
选择阶段：初始化选择第一个活动（排序后最早结束的），然后遍历剩余活动。若当前活动的开始时间不早于已选活动的结束时间，则选择该活动，并更新已选活动的指针。通过这种策略，保证每一步选择都是局部最优，最终得到全局最优解。
该算法的时间复杂度主要由排序决定，为O(n log n)，适用于题目中的最大数据规模。
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
https://edu.csdn.net/course/detail/41081 点击跳转
3、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转
4、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
