500万彩票

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

发布时间:2020-06-29 11:00:48
阅读量:39
作者:猎维人工智能培训
C++和C面试题

我们按照左端点对区间[x,y]排序。

对区间[x1,y1]我们考察所有它“右面”的区间,更新最大值。

对[x2,y2] x2 >= x1

500万彩票(1) 如果y2 >= y1

则更右面的区间和[x1,y1]的重叠部分不会超过这个区间。 所以候选答案是max(y1 - x2, 0),然后我们可以删掉[x1, y1]

(2) 如果y2 < y1

这说明答案至少是(y2 - x2)了,这个区间没有继续存在的意义,删掉它。

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

更多资讯