可能的面试问题：如何查找所有重叠区间 [英] Possible Interview Question: How to Find All Overlapping Intervals

问题描述

这不是一个面试问题的本身的，因为我在我的项目遇到了这一点，但我想它可能是一个不错的intervew问题。

It's not an interview question per se, as I came across this in my project, but I figured it could be a decent intervew question.

您有N对区间，比如说整数。你需要来识别的相互O（N）时间上重叠的所有间隔。例如，如果你有

You have N pairs of intervals, say integers. You're required to indentify all intervals that overlap with each other in O(N) time. For example, if you have

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

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

答案是{1,3}，{12,14}，{2,4}，{13,15}。注意，不需要将它们分组，因此结果可以在任何顺序像在示例

the answer is {1, 3}, {12, 14}, {2, 4}, {13, 15}. Note that you don't need to group them, so the result can be in any order like in the example.

我只是扔在O（N）的时间，因为KMP算法需要O（N）的字符串搜索。 ：D

I just threw in O(N) time because the KMP algorithm takes O(N) for string search. :D

最好的我想出了，我使用的是什么，现在该项目为O（N ^ 2）。是啊，蛮力是pretty的悲伤，但没有人抱怨，所以我不会重构它。 ：P不过，我很好奇，如果有较大的头脑有一个更好的解决方案。

The best I came up with and what I'm using right now in the project is O(N^2). Yeah, brute force is pretty sad, but no one complains so I won't refactor it. :P Still, I was curious if a greater mind has a more elegant solution.

推荐答案

扔区间的端点到一个数组，将它们标记为无论是开始 - 或终点。您可以按照通过将终点前的启动点突破的关系，如果间隔关闭，或者反过来，如果他们是半开的。

Throw the endpoints of the intervals into an array, marking them as either start- or end-points. Sort them by breaking ties by placing end-points before start-points if the intervals are closed, or the other way around if they're half-open.

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E

然后通过列表循环，跟踪有多少时间间隔是在（这相当于加工的终点减去起点数号）。每当我们到了一个起始点，而我们已经在一个区间，这意味着我们必须有重叠的区间。

Then iterate through the list, keeping track of how many intervals we're in (this equates to number of start-points processed minus number of end-points). Whenever we hit a start-point while we have are already in an interval, this means we must have overlapping intervals.

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E
    ^                          ^
   overlap                    overlap

我们可以找到它的时间间隔与通过存储数据以及结束点，并跟踪这些重叠的区间我们在

We can find which intervals overlap with which by storing data alongside the end-points, and keeping track of which intervals we're in.

这是一个O（N logN）的解决方案，整理是主要因素。

This is an O(N logN) solution, with sorting being the main factor.

这篇关于可能的面试问题：如何查找所有重叠区间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！