AcWing 905. 区间选点
原题链接
简单
C++ 代码
#include<iostream>
#include<bits/stdc++.h>
#define l first
#define r second
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
PII a[N];
int n;
int vis[N];//标记数组
bool cmp(PII a ,PII b)
{
return a.r<b.r;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
scanf("%d%d",&a[i].l,&a[i].r);
sort(a,a+n,cmp);//右端点排序
int cnt=0;
for(int i=0;i<n;i++)
{
if(!vis[i])
{
vis[i]=1;//没被先前点覆盖,就新增一点来标记该区间
cnt++;//点数加一
for(int j=i+1;j<n;j++)//遍历后面区间
if(a[i].r>=a[j].l) vis[j]=1;//若也被该点覆盖就标记
}
}
cout<<cnt;
return 0;
}