AcWing 905. 区间选点
原题链接
简单
作者:
菜鸡一个
,
2019-07-23 08:51:18
,
所有人可见
,
阅读 1563
思路:
- 将每个区间按右端点从小到大排序
- 从前往后依次枚举每个区间,如果当前区间中已经包含,则pass
否则,选择当前区间的右端点
结构体排序
struct Range
{
int l;
int r;
}p[N];
bool cmp(const Range &a, const Range &b)
{
return a.r<b.r;
}
枚举每个区间
int res=0,end=-2e9;
for(int i=0;i<n;i++)
{
if(p[i].l>end)
{
res++;
end=p[i].r;
}
}
Ac代码
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 100010;
struct Range
{
int l, r;
}p[N];
bool cmp(const Range &a, const Range &b)
{
return a.r < b.r;
}
int n;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&p[i].l,&p[i].r);
}
sort(p, p+n, cmp);
int res = 0,end = -2e9;
for(int i=0;i<n;i++)
{
if(p[i].l>end)
{
end=p[i].r;
res++;
}
}
printf("%d\n",res);
return 0;
}
非常清晰
好清晰