想要改善这篇文章吗？ 提供此问题的详细答案，包括引文和答案正确的解释。答案不够详细的答案可能会被编辑或删除。
正如我在项目中遇到的那样，这 本身 不是一个采访问题，但我认为这可能是一个不错的干预问题。
您有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不过，我很好奇，如果一个更大的头脑有一个更优雅的解决方案。
将间隔的端点放入数组中，将其标记为起点或终点。如果间隔是封闭的，则通过将端点放在起点之前来打破平局来对它们进行排序，如果间隔是半开放的，则将它们放在相反的位置。
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）解决方案，其中排序是主要因素。
