基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题
收藏
关注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
题意很清楚,就是找到最长的重复长度然后输出.
这道题对初学者看似很复杂，其实认真分析就会发现很简单。
首先： 先将输入的区间起点按升序排序，若起点相同则按终点降序排序
比如5组区间：（1 5）（2 4）（2 8）（3 7）（7 9）
按上面所述排序： （1 5） (2 8) （2 4） （3 7） （7 9）
这样很直观，为什么要起点升序，起点相同则按终点降序排序
起点升序很容易理解，我们要找区间覆盖最大长度。
起点相同则按终点降序排序 明显（1 5） （2 8） 区间覆盖长度大于 （1 5） (2 4) (别忘了这可是一道贪心算法题，从最接近最优解出发)
接下来考录主要考虑两个方面： 1区间覆盖 2区间包含跟不包含（一起处理）
（应该选定一个参考区间）
1 区间覆盖： 直接是小区间的距离（2 8）（2 4） 直接是4-2=2；
2 区间包含跟不包含： 区间包含，就是第一个区间终点跟第二个区间起点的差值，eg: (1 5) (2 8) 即5-2=3
假如（1 5）是参考区间，那么比较完（1 5） （2 8）。参考区间应该为下一个区间，即（2 8）.
因为后面的区间起始点都不比（2 8）小（起点升序）。又因为区间包含，就是第一个区间终点跟第二个区间起点的差值。那么后面的区间跟（1 5)区间覆盖长度都没有比（2 8）区间覆盖长度大。。显然的，说起来很绕。所以这时再以（1 5）作为参考区间没有意义了。
为方便起见，就选取下一个区间作为参考区间,即（2 8）.
1.先将输入的区间起点按升序排序，若起点相同则按终点降序排序
2.分两部分处理：区间覆盖 区间包含跟不包含
1 #include <bits/stdc++.h> 2 #define N 50005 3 using namespace std; 4 struct Node{ 5 int start,end; 6 }node[N]; 7 bool cmp(Node x,Node y){ 8 if(x.start==y.start) 9 return x.end>y.end; 10 return x.start<y.start; 11 } 12 int main(){ 13 int n,ans=0; 14 scanf("%d",&n); 15 for(int i=0;i<n;i++) 16 scanf("%d%d",&node[i].start,&node[i].end); 17 sort(node,node+n,cmp); 18 Node cnt=node[0]; 19 for(int i=1;i<n;i++){ 20 if(cnt.end>=node[i].end) 21 ans=max(ans,node[i].end-node[i].start); 22 else{ 23 ans=max(ans,cnt.end-node[i].start); 24 cnt=node[i]; 25 } 26 } 27 printf("%d ",ans); 28 return 0; 29 }