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

问题描述

这不是面试问题本身，因为我在我的项目中遇到过这个问题，但我认为这可能是一个不错的面试问题.

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).是的，蛮力是很可悲的，但没有人抱怨所以我不会重构它.: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 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屋！