线段的重叠(感觉这是一个错题)

写这篇文章是因为这个题有一点弄不懂,就是下面我说的这个,感觉是一道错题。

 

题目:

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

输出最长重复区间的长度。

Sample Input

5
1 5
2 4
2 8
3 7
7 9

Sample Output

4
现在有五条线段用 s0,s1,s2,s3,s4来表示
编号    起点x1  终点x2
s0      1       5
s1      2       4
s2      2       6
s3      4       9
s4      7       9
那么我们可以看到最长的重叠度应该是 s0 与 s2 重叠长度是 5-2 = 3 。
那么如果按AC代码来算的话
首先一个 int ans = 0;
然后是一个 struct node temp = s0;
循环是 for( int i=1; i<5; i++ )
之后判断如果是后一条线段是否完全在前一条线段之内
如果是  ans = max(ans, s[i].x2 - s[i].x1);
如果不是 ans = max(ans, temp.x2 - s[i].x1);
然后temp = s[i];
那么ans的值得变化是
起始:             ans = 0;
i = 1, temp = s0   ans = max(0, 4-2) = 2;
i = 2, temp = s1   ans = max(2, 4-2) = 2;
i = 3, temp = s2   ans = max(2, 6-4) = 2;
i = 4, temp = s3   ans = max(2, 9-7) = 2;
最终的结果就是 ans = 2;
但是我们明显知道的是 最长的重叠是s0与s2的重叠长度 5 - 2 = 3;
即最终的结果应该是3才对。
 
也很可能是我太菜,想不明白,还请留言帮忙指出错误

更详细的分析看我另一篇文章: click here !!!

全部评论

相关推荐

太难了,双9bg也被刷
投递韶音科技等公司10个岗位
点赞 评论 收藏
分享
Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
07-22 11:12
门头沟学院 Java
不是,我就随手投的怎么还真发面试啊
皮格吉:大厂特别快的——来自已经被共享中
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务