題目

X軸上有N條線段，每條線段有1個起點S和終點E。最多能夠選出多少條互不重疊的線段。（注：起點或終點重疊，不算重疊）。
例如：[1 5][2 3][3 6]，可以選[2 3][3 6]，這2條線段互不重疊。

輸入

第1行：1個數N，線段的數量(2 <= N <= 10000)
第2 - N + 1行：每行2個數，線段的起點和終點(-10^9 <= S,E <= 10^9)

輸出

輸出最多可以選擇的線段數量。

輸入樣例

3
1 5
2 3
3 6

輸出樣例

2

思路：

要選擇最多的線段數量，那么按照線段的起點、終點進行排序后，從頭到尾進行選擇即可

由于線段的起點和終點可能是負數，那么根據數據范圍將輸入的每條線段整體右移 1E9

源程序

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 50000+5; const int dx[] = {-1,1,0,0}; const int dy[] = {0,0,-1,1}; using namespace std;struct Node{LL start;LL endd; }a[N]; bool cmp(Node a,Node b){if(a.endd==b.endd)return a.start<b.start;return a.endd<b.endd; } int main(){int n;scanf("%d",&n);for(int i=0;i<n;++i){scanf("%lld%lld",&a[i].start,&a[i].endd);a[i].start+=1E9;a[i].endd+=1E9;}sort(a,a+n,cmp);LL k=a[0].endd;int res=1;for(int i=1;i<n;i++){if(a[i].start>=k){res++;k=a[i].endd;}}printf("%d\n",res);return 0; }

?

總結

以上是生活随笔為你收集整理的不重叠的线段（51Nod-1133）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。