1、B站视频链接:A29 贪心算法 P1803 线段覆盖_哔哩哔哩_bilibili
题目链接:凌乱的yyy / 线段覆盖 - 洛谷
#include <bits/stdc++.h>
using namespace std;
struct line{
int l,r;
bool operator<(line &b){
return r<b.r;//重载小于号,按右端点排序
}
}L[1000005];
int n,last,cnt;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&L[i].l,&L[i].r);
}
sort(L+1,L+n+1);//排序,右端点越小,总的个数就越多
for(int i=1;i<=n;i++){
if(last<=L[i].l){//上一个的右端点小于当前的左端点
last=L[i].r;//成立则选择当前段并变成last
cnt++;
}
}
printf("%d\n",cnt);
return 0;
}