題目描述
數(shù)軸上有 n 條線段，選取其中 k 條線段使得這 k 條線段兩兩沒有重合部分，問 k 最大為多少。

輸入格式
第一行為一個(gè)正整數(shù) n；

在接下來的 n 行中，每行有 2 個(gè)數(shù) ai,bi，描述每條線段。

輸出格式
輸出一個(gè)整數(shù)，為 k 的最大值。

樣例
Input Output
3
0 2
2 4
1 3
2
數(shù)據(jù)范圍與提示
對(duì)于 20% 的數(shù)據(jù)，n≤10；

對(duì)于 50% 的數(shù)據(jù)，n≤103；

對(duì)于 70% 的數(shù)據(jù)，n≤105；

對(duì)于 100% 的數(shù)據(jù)，n≤106, 0≤ai<bi≤106。
思路：按照右端點(diǎn)從小到大排序，然后選取即可。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e6+100; struct node{int x,y;bool operator<(const node&a)const{return y<a.y;} }p[maxx]; int n;int main() {scanf("%d",&n);for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;sort(p+1,p+1+n);int cnt=0;int dis=p[1].y;cnt++;int i,j=2;while(1){for(i=j;i<=n;i++){if(p[i].x>=dis){j=i;dis=p[i].y;cnt++;break;}}if(i==n+1) break;}cout<<cnt<<endl;return 0; }

努力加油a啊

總結(jié)

以上是生活随笔為你收集整理的线段 LibreOJ - 10007（贪心）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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