重叠间隔
假设给定一组间隔（长度不一定是整数）。如何确定给定集合中任意两个间隔之间是否存在重叠？我想知道间隔数是否有线性解。
PS：不是硬件问题。这是我在采访一家公司时被问到的。
Assume that you are given a set of intervals (not necessarily integral in length). How do you determine if there is an overlap between any two intervals in the given set? I am wondering if there is a linear solution in the number of intervals.
P.S: Not a HW problem. This was asked in one of my interviews with a company.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果所有间隔都按起点排序，那么很容易检查其中两个间隔是否重叠。只需扫描所有区间，保留我们从之前区间得到的最大终点，如果最大终点>当前起点，然后我们得到了重叠。如果我们没有获得所有间隔的重叠，那么就没有重叠。
如果间隔没有排序。那么一般来说，检测重叠的下限是 O(n logn)。因为当所有区间都有start_point = end_point时，那么问题就简化为清晰度问题。 http://en.wikipedia.org/wiki/Element_distinctness_problem。所有基于比较的算法都需要 O(n log n) 时间。
然而，如果所有区间的点都是离散的，并且在某个范围[0,L)内，例如一天中的秒数是从0到60*60*24，那么可以用O(n+L)线性求解时间和 O(L) 空间。
这个想法是，每个区间 i 都有一个起点 si 和终点 ei。我们创建一个数组 a = new int[L]。对于每个区间 i，我们将 a[si] 加 1 到 a[ei]。然后我们检查是否存在 a[j] > 1，如果是这样，我们就得到了重叠。
最简单的方法是使用 2 个 for 循环，时间复杂度为 O(n*L)。在Programming Peals中有一个聪明的算法可以将运行时间减少到O(n+L)。如果您有兴趣并且这正是您的面试官想要的，我可以向您展示详细信息。
所以，这是我所知道的3种情况。您认为哪一个适合您的问题。
If all the intervals are sorted by start point, then it's easy to check whether there is two of them overlap. Just scan through all the intervals, keep the maximum end point we got from previous intervals, and if the max end point > current start point, then we got a overlap. If we haven't get overlap for all intervals, then there is no overlap.
If the intervals are not sorted. Then in general the lower bound to detect overlap is O(n logn). Because when all intervals have start_point = end_point, then the problem is reduced to distinctness problem. http://en.wikipedia.org/wiki/Element_distinctness_problem. All comparison based algorithm need O(n log n) time.
However, if the points of all intervals are discrete and in some certain range [0,L), e.g. the seconds in a day is from 0 to 60*60*24, then it can be solved in O(n+L) linear time and O(L) space.
The idea is that, each interval i has a start point si and end point ei. We create an array a = new int[L]. For each interval i, we add 1 for a[si] to a[ei]. Then we check whether there is an a[j] > 1, if so we get an overlap.
The most naive method is using 2 for loops and the time complexity is O(n*L). In Programming Peals there is a clever algorithm which could reduce the running time to O(n+L). If you are interested and this is what your interviewer wants, I can show you the detail.
So, this is the 3 situations I know. Which one do you think fits your problem.
查看名为 Interval Tree 的数据结构。这用于查找重叠间隔。
如果间隔按其起始值排序，则这是一个 O(n) 复杂度的简单问题。
另一种方法是标记大小为 m 的数组中的每个间隔，并逐步检查它们是否重叠。数组的大小（例如 m）可以在 O(n) 中确定，但空间和时间要求将是 O(m)。
Look into the data structure called Interval Tree. This is used to find overlapping intervals.
If the intervals are sorted by their starting values, this is a simple problem in O(n).
An alternative would be to mark each interval in an array of size m and progressively check if they overlap. The size of the array (say m) can be determined in O(n), but the space and time requirement would be O(m).