假设给定了一组区间(长度不一定是整数)。您如何确定给定集合中任意两个区间之间是否存在重叠？我想知道间隔数是否有线性解。
P.S:不是硬件问题。这是我在采访一家公司时被问到的。
最佳答案
如果所有区间都按起点排序，那么很容易检查是否有两个区间重叠。只需扫描所有间隔，保留我们从先前间隔获得的最大终点，如果最大终点 > 当前起点，则我们得到重叠。如果我们没有得到所有间隔的重叠，那么就没有重叠。
如果区间没有排序。那么通常检测重叠的下限是 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 种情况。你认为哪一个适合你的问题。
关于algorithm - 重叠区间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5752990/