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

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

按起点对间隔进行排序.然后折叠该列表,如果它们重叠,则将每个间隔与其邻居(即(1,4),(2,6) - >(1,6))合并.结果列表包含没有重叠伙伴的那些间隔.从原始列表中筛选出这些内容.

在初始排序操作之后,这是线性的,可以使用任何(n log n)算法完成.不确定你是如何解决这个问题的.如果您利用第一个操作的输入和输出的已排序顺序,即使最后的"过滤重复"操作也是线性的.

这是Haskell中的一个实现:

-- Given a list of intervals, select those which overlap with at least one other inteval in the set.
import Data.List

type Interval = (Integer, Integer)

overlap (a1,b1)(a2,b2) | b1 < a2 = False
                       | b2 < a1 = False
                       | otherwise = True

mergeIntervals (a1,b1)(a2,b2) = (min a1 a2, max b1 b2)

sortIntervals::[Interval]->[Interval]
sortIntervals = sortBy (\(a1,b1)(a2,b2)->(compare a1 a2))

sortedDifference::[Interval]->[Interval]->[Interval]
sortedDifference [] _ = []
sortedDifference x [] = x
sortedDifference (x:xs)(y:ys) | x == y = sortedDifference xs ys
                              | x < y  = x:(sortedDifference xs (y:ys))
                              | y < x  = sortedDifference (x:xs) ys

groupIntervals::[Interval]->[Interval]
groupIntervals = foldr couldCombine []
  where couldCombine next [] = [next]
        couldCombine next (x:xs) | overlap next x = (mergeIntervals x next):xs
                                 | otherwise = next:x:xs

findOverlapped::[Interval]->[Interval]
findOverlapped intervals = sortedDifference sorted (groupIntervals sorted)
  where sorted = sortIntervals intervals

sample = [(1,3),(12,14),(2,4),(13,15),(5,10)]

Answer 3

针对互联网问题的标准方法是根据起点对它们进行排序,然后从头到尾进行排序.O(n*logn)(O(n)如果已经排序)

end = 0;
for (current in intervals) {
    if current.start < end {
        // there's an intersection!
        // 'current' intersects with some interval before it
        ...
    }
    end = max(end, current.end)
}

Answer 4

不确定O（N），但是如果我们先按每个元组中的第一个数字对它们进行排序，然后顺序查找那些元组的第一个数字大于前一个元组中看到的最大数字的那个，那该怎么办？不与下一个元组重叠。

因此，您首先会得到：

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

因为4（最大）<5和10 <12，{5，10}是隔离的。

这将需要我们跟踪遇到的最大数字，并且每次找到起始编号较大的元组时，都要检查其是否与下一个重叠。

这将取决于排序算法的效率，因为后者的过程将是O（N）