51nod——1091 线段的重叠(排序，贪心）

1091 线段的重叠 题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=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 输出最长重复区间的长度。 Input示例 5 1 5 2 4 2 8 3 7 7 9 Output示例 4 贪心算法,将所有线段按起始点有小到大排列，起始点相同按结尾从大到小排列，然后判断相邻两线段重叠部分，并取最大值，每次查找后，都要更新最大结尾范围，为查找后线段结尾的最大值 #include<stdio.h> #include<iostream> #include<algorithm> using namespace std; struct node { int l,r; }no[100000]; bool cmp(node a,node b)//排序 { if(a.l!=b.l) return a.l<b.l; else return a.r>b.r; } int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d",&no[i].l,&no[i].r); } sort(no,no+n,cmp); int k=0,ans=no[0].r; for(int i=1;i<n;i++) { k=max(k,min(no[i].r,ans)-no[i].l);//取最大值 ans=max(no[i].r,ans); //更新结尾范围 } printf("%d\n",k); }