首页 > 代码库 > 51Nod 1091 线段的重叠(贪心+区间相关
51Nod 1091 线段的重叠(贪心+区间相关
1091 线段的重叠
X轴上有N条线段，每条线段包括1个起点和终点。线段的重叠是这样来算的，[10 20]和[12 25]的重叠部分为[12 20]。
给出N条线段的起点和终点，从中选出2条线段，这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠，输出0。
Input
第1行：线段的数量N(2 <= N <= 50000)。第2 - N + 1行：每行2个数，线段的起点和终点。(0 <= s , e <= 10^9)
Output
输出最长重复区间的长度。
看的别人的题解 然后发现人家和我是同年级的 不过水平比我高了不少 以后还是少刷水题，多长知识
思路：
1.先将输入的区间起点按升序排序，若起点相同则按终点降序排序
2.分两部分处理：区间覆盖 比如 [2，8][2，4] 区间有交集 // 比如[2,8] [3,9]
#include <bits/stdc++.h>using namespace std;const int maxn = 5e4+10;struct node{ int l,r; bool operator <(const node & a)const{ if(l !=a.l ) return l < a.l; return r>a.r; }}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); node ans = s[0]; int res = 0; for(int i=1;i<n;i++) { if(ans.r > s[i].r)//比如 [2，8][2，4] res = max(res,s[i].r-s[i].l); else { res = max(res,ans.r - s[i].l); // [2,8] [3,9] ans = s[i]; } } printf("%d\n",res); return 0;}
51Nod 1091 线段的重叠(贪心+区间相关
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。