面试题:在一维坐标轴上有n个区间段,求重合区间最长的两个区间段。


在一维坐标轴上有n个区间段,求重合区间最长的两个区间段?

解析:

我们按照左端点对区间[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)的。

为了帮助大家备战秋招,给大家准备了一场限时免费的大厂面试辅导专场讲座。

面试套路都在这儿了,限时【免费】送500个名额,准备校招和跳槽的同学,答应我一定看完再去面试哟!
大厂面试辅导.png
已邀请:

要回复问题请先登录注册

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

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