#每日一面BAT#第23题 区间最大重叠


在一维坐标轴上有n个区间段,求重合区间最长的两个区间段。
已邀请:

cpcs - 诚实努力

赞同来自: 张鹏是个蔡小豆 ybdesire


答案:
我们按照左端点对区间[x,y]排序。
对区间[x1,y1]我们考察所有它“右面”的区间,更新最大值。
对[x2,y2] x2 >= x1
(1) 如果y2 >= y1
则更右面的区间和[x1,y1]的重叠部分不会超过这个区间。 所以候选答案是max(y1 - x2, 0),然后我们可以删掉[x1, y1]
(2) 如果y2 < y1
这说明答案至少是(y2 - x2)了,这个区间没有继续存在的意义,删掉它。

两种情况我们都可以删掉一条线段,所以时间复杂度是O(n)的。

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~