间隔重叠

Question

假设给你一组间隔(长度不一定是整数).如何确定给定集合中任何两个间隔之间是否存在重叠？我想知道是否有间隔数的线性解决方案.

PS:不是硬件问题.在我对一家公司的采访中提到了这一点.

Answer 1

如果所有间隔都按起点排序,那么很容易检查是否有两个重叠.只扫描所有间隔,保持我们从前一个间隔得到的最大终点,如果最大终点>当前​​起点,那么我们得到重叠.如果我们没有为所有间隔重叠,则没有重叠.

如果间隔未排序.然后通常检测重叠的下限是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,我们将[si]加1加到[ei].然后我们检查是否有[j]> 1,如果是,我们得到重叠.

最天真的方法是使用2 for循环,时间复杂度为O(n*L).在Programming Peals中有一个聪明的算法可以将运行时间减少到O(n + L).如果您有兴趣并且这是您的面试官想要的,我可以向您展示详细信息.

所以,这就是我所知道的三种情况.您认为哪一个适合您的问题.

Answer 2

查看称为“区间树”的数据结构。这用于查找重叠间隔。

如果间隔按其起始值排序，则这是一个 O(n) 复杂度的简单问题。

另一种方法是标记大小为 m 的数组中的每个间隔，并逐步检查它们是否重叠。数组的大小（比如 m）可以在 O(n) 中确定，但空间和时间要求将是 O(m)。