线段覆盖加强版（快速+贪心）

在一个数轴上有n条线段，线段的端点均为数轴上的整数点。

现在请你删除尽量少的线段，使得剩下的线段不相交。

输出剩下的线段数

输入规模较大，建议使用读入优化
输入
第一行一个整数n
接下来n行，每行两个整数x,y表示线段的端点坐标
输出
一行一个整数表示剩下的线段的最大数量。

数据范围
对于40%的数据： n<=3000
对于80%的数据： n<=100000
对于100%的数据： n<=2000000，0<=端点坐标<=1000000
输入样例
输入样例1：
3
6 3
1 3
2 5
输入样例2:
10
90 351
578 742
99 836
212 606
552 89
585 20
495 803
750 760
874 878
550 273
输入样例3:
10
650 154
598 443
325 950
144 908
454 284
728 46
506 222
475 826
743 198
340 998
输出样例
输出样例1：
2
输出样例2:
4
输出样例3:
2

情况：两个测试用例超时

问题：数组开小了，刚开始开了1百万的数组，发现数据最大200万const int maxn=2e6+10。

分析

ac代码

#include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int maxn=2e6+10;struct node{int left,right; }a[maxn];//快读 int read(){int k=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')//读入负数 f=-1;c=getchar();}while(c>='0'&&c<='9'){k=10*k+c-'0';c=getchar();}return f*k; }bool cmp(node a,node b){if(a.left==b.left)return a.right<b.right; return a.left<b.left; } int main(){int n,x,y,result=0;cin>>n;for(int i=0;i<n;++i){//小的放前面 x=read(),y=read();if(x>y) x^=y^=x^=y;//swap也不行 a[i].left=x,a[i].right=y;}sort(a,a+n,cmp);//左端点从小到大排列result++;//第一条一定放int now=a[0].right;//保存当前右端点for(int i=1;i<n;i++){if(a[i].left>=now){result++;now=a[i].right;//更新右端点 }else{if(a[i].right<=now){//完全覆盖 //贪心，留着短的那一条now=a[i].right; }//else //没有完全覆盖，舍弃当前线段，不做处理 }} cout<<result<<endl;}

总结

以上是生活随笔为你收集整理的线段覆盖加强版（快速+贪心）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。