在一個數(shù)軸上有n條線段，線段的端點均為數(shù)軸上的整數(shù)點。

現(xiàn)在請你刪除盡量少的線段，使得剩下的線段不相交。

輸出剩下的線段數(shù)

輸入規(guī)模較大，建議使用讀入優(yōu)化
輸入
第一行一個整數(shù)n
接下來n行，每行兩個整數(shù)x,y表示線段的端點坐標
輸出
一行一個整數(shù)表示剩下的線段的最大數(shù)量。

數(shù)據(jù)范圍
對于40%的數(shù)據(jù)： n<=3000
對于80%的數(shù)據(jù)： n<=100000
對于100%的數(shù)據(jù)： 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

情況：兩個測試用例超時

問題：數(shù)組開小了，剛開始開了1百萬的數(shù)組，發(fā)現(xiàn)數(shù)據(jù)最大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=='-')//讀入負數(shù) 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;}

總結(jié)

以上是生活随笔為你收集整理的线段覆盖加强版（快速+贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。