假设您将得到一组间隔（不一定是不可或缺的长度）。如何确定是否存在在给定集合中的任意两个间隔之间的重叠？我想知道如果在间隔数线性解决方案。

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：不是一个硬件问题。这是在问我采访了公司。

P.S: Not a HW problem. This was asked in one of my interviews with a company.

推荐答案

如果所有的间隔由起点排序，那么可以很容易地检查是否有他们两个人重叠。在所有的时间间隔只需扫描，让我们从previous间隔得到了最大的终点，如果最大终点>当前​​的起点，那么我们得到了一个重叠。如果我们没有得到重叠的所有间隔，那么就没有重叠。

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.

如果间隔不排序。然后在一般下界来检测重叠是O（n logn）时间。因为当所有的时间间隔都start_point = end_point，那么问题就减少到明显的问题。 http://en.wikipedia.org/wiki/Element_distinctness_problem.所有基于比较算法需要为O（n log n）的时间。

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.

然而，如果所有的间隔的点是离散的，在一定的范围[0，L），如在一天的秒是从0到60 * 60 * 24，那么可以为O解决第（n + L）的线性时间和O（L）的空间。

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.

的思想是，每个间隔i有一个起点Si和结束点的ei。我们创建一个数组A =新的INT [L]。对于每一个区间I，我们加1的[SI]到[EI]。然后我们检查是否有一个[J]> 1，如果是这样，我们得到的重叠。

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.

最幼稚的方法是使用2 for循环的时间复杂度为O（n * L）。在编程Peals有一个聪明的算法可以在运行时间缩短为O（n + 1）。如果你有兴趣，这是你的面试官想要什么，我可以告诉你的细节。

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.

所以，这是3的情况下，我知道。哪一个你觉得适合你的问题。

So, this is the 3 situations I know. Which one do you think fits your problem.