可能的面试问题：如何找到所有重叠的间隔

Question

正如我在项目中遇到的那样，这本身不是一个采访问题，但我认为这可能是一个不错的干预问题。

您有N对间隔，例如整数。您需要确定在O（N）时间内彼此重叠的所有间隔。例如，如果您有

{1，3} {12，14} {2，4} {13，15} {5，10}

答案是{1、3}，{12、14}，{2、4}，{13、15}。请注意，您无需对其进行分组，因此结果可以按示例中的任何顺序排列。

我只是花了O（N）的时间，因为KMP算法将O（N）用于字符串搜索。：D

我想到的最好的东西是我现在在项目中使用的是O（N ^ 2）。是的，蛮力很可悲，但是没有人抱怨，所以我不会重构它。：P不过，我很好奇，如果一个更大的头脑有一个更优雅的解决方案。

Answer 1

将间隔的端点放入数组中，将其标记为起点或终点。如果间隔是封闭的，则通过将端点放在起点之前来打破平局来对它们进行排序，如果间隔是半开放的，则将它们放在相反的位置。1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E然后遍历该列表，跟踪我们处于多少间隔（这等于已处理的起点数减去终点数）。每当我们已经处于一个间隔中而到达起点时，这意味着我们必须具有重叠的间隔。1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E    ^                          ^   overlap                    overlap通过在端点旁边存储数据并跟踪我们所处的间隔，我们可以找到哪些间隔与哪些间隔重叠。这是一个O（N logN）解决方案，其中排序是主要因素。

Answer 2

在线间隔问题的标准方法是根据起点对它们进行排序，然后从头到尾走动。O(n*logn)（O(n)如果已经排序）end = 0;for (current in intervals) {&nbsp; &nbsp; if current.start < end {&nbsp; &nbsp; &nbsp; &nbsp; // there's an intersection!&nbsp; &nbsp; &nbsp; &nbsp; // 'current' intersects with some interval before it&nbsp; &nbsp; &nbsp; &nbsp; ...&nbsp; &nbsp; }&nbsp; &nbsp; end = max(end, current.end)}