题目描述
给定N个闭区间[ai,bi],请你在数轴上选择若干区间,使得选中的区间之间互不相交(包括端点)。
输出可选取区间的最大数量。
样例
输入样例:
3
-1 1
2 4
3 5
输出样例:
2
题目心得
贪心这个算法没有固定的模板,只有思想。
大部分时候听到贪心都下意识认为是暴力算法,因为这个思路不需要去精心思考很暴力就想到了?(貌似也有复杂度的原因)
这个算法除非真的愿意去花时间来证明自己是对的不然贪心多少沾点运气成分。
排序
这道题目为什么排序Y?
这个问题很想当然,因为刚开始时我是排序X的。结果很明显错了。
所以模拟一下X排序和Y排序的结果来看为什么。
按照X排序
当前的X一定比前面所有的X大。
但是Y节点是不能保障的,因为当前Y一定比当前X大所以前面的Y并非比当前的X小。
但如果前面的Y比当前X大时则是无效反之则有。
即使这样也还是有问题只要前面有一个Y比当前X大则代表这个答案只能存放在当前位置并不能累计到下个去使用。
(反正就是很麻烦吧唉,还没有想出来怎么使用X排序来写出来这道题目。)
按照Y排序
当前的Y一定比前面所有的Y大。
所以当前Y一定比前面所有的X大,所以当前X比前面X小时是无效情况,反之则是有效答案可以累积。
保存最大的X则可以让最优解一直累积下去。
代码
#include<cstdio>
#include<algorithm>
using namespace std;
const int sz=1e5+1;
int n;
struct nd{int x,y;}a[sz];
int cmp(nd a,nd b){return a.y<b.y;}
int main()
{
int i,ss=-1e9,s=0,x,y;
scanf("%d",&n);
for(i=1;i<=n;++i)scanf("%d%d",&x,&y),a[i].x=x,a[i].y=y;
sort(a+1,a+n+1,cmp);
for(i=1;i<=n;++i)if(a[i].x>ss)++s,ss=a[i].y;
printf("%d",s);
return 0;
}
请问一下,按照y排序那里,应该是——当前X比前面y小时是无效情况,反之则是有效答案可以累积吧?