首页 > 代码库 > 51NOD 1133 不重叠的线段
51NOD 1133 不重叠的线段
1133 不重叠的线段
X轴上有N条线段，每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。（注：起点或终点重叠，不算重叠）。
例如：[1 5][2 3][3 6]，可以选[2 3][3 6]，这2条线段互不重叠。
Input
第1行：1个数N，线段的数量(2 <= N <= 10000)第2 - N + 1行：每行2个数，线段的起点和终点(-10^9 <= S,E <= 10^9)
Output
输出最多可以选择的线段数量。
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5+10;struct node{ int l,r; bool operator<(const node & a)const { if(a.r != r) return r < a.r; return l < a.l; }}s[maxn];int main (){ int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d %d",&s[i].l,&s[i].r); sort(s,s+n); int ans = s[0].r,res =1; for(int i=1;i<n;i++){ if(ans <= s[i].l){ ans = s[i].r; res++; } } printf("%d\n",res); return 0;}
51NOD 1133 不重叠的线段
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。