最大不相交区间数==最少覆盖区间点数
相似题目传送门(双倍经验)
我假设大家都是从这道题过来的好吧
//来自算法基础课
为什么最大不相交区间数==最少覆盖区间点数呢?
因为如果几个区间能被同一个点覆盖
说明他们相交了
所以有几个点就是有几个不相交区间
区间问题的贪心一般都是上来先按左端点或者右端点排序
然后手动模拟一下人脑怎么贪心的
看看能不能搞出来什么性质
猜出来一个贪心策略的话多找几组样例试试正确性
当然你能严格证明就能牛逼了
当你觉得他是贪心题的时候
千万不要轻易相信题目给的样例
代码跟上面那个题一毛一样_(:з」∠)_
#include<bits/stdc++.h>
using namespace std;
int n,tmp=-214783646,cnt;
struct node{
int l,r;
}d[100005];
bool cmp(node a,node b) {
return a.r < b.r;
}
int main(){
scanf("%d",&n);
for(register int i=1; i<=n; i++) scanf("%d%d",&d[i].l,&d[i].r);
sort(d+1,d+1+n,cmp);
for(register int i=1; i<=n; i++)
if(tmp>=d[i].l && tmp<=d[i].r) continue; //注意是闭区间,别忘了等号
else tmp = d[i].r, cnt++;
printf("%d\n",cnt);
return 0;
}
好家伙,你这个传送门,搁这原地TP呢
搁这死循环!
千万不要轻易相信题目给的样例 太对了~
为什么呢?
大佬 这个是啥意思啊?
借用一下解释,谢谢大佬