贪心->如果有一堆苹果,那么先吃最新鲜的那个
区间选点 — 贪心详解
一般区间问题都会先排个序,这个得安排上
1.将每个区间按照右端点从小到大排序
2.从前往后依次枚举每个区间
3.如果当前区间已经包含点,则直接舍弃,否则选择当前区间的右端点
首先明确一下我们找到的解一定是小于任取出来的解的,因为我们的解是最小值,所以此处的ans(最终解)<=cnt(任意解)
随后再次证明ans>=cnt即可
算法1
定义一个结构体方便表示数组两边,用二维数组也可以。
先初始化res以及ed右端点
如果比右端点大那么就res+1同时再下一个数据段取最右端即可
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
struct Range//定义一个结构体表示区间
{
int l,r;
bool operator<(const Range &W)const
{
return r<W.r;
}
}range[N];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int l,r;
scanf("%d%d",&l,&r);
range[i]={l,r};//还能这么玩???
}
sort(range,range+n);
int res=0,ed=-2e9;//存结果,存上个点的下标
for(int i=0;i<n;i++)
{
if(range[i].l>ed)
{
res++;
ed=range[i].r;
}
}
printf("%d\n",res);
return 0;
}