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

 

题目:

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 !!!