这不是一个典型的面试问题，因为我在项目中遇到了这个问题，但我认为这可能是一个不错的面试问题。
给定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)的解决方案，其中排序是主要因素。
按起点对区间进行排序。然后折叠这个列表，如果相邻的两个区间重叠（即 (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)]
overlap (_, b1) (a2,_) | b1 > a2 = True | otherwise = False或者只是:overlap (_, b1) (a2,_) = b1 > a2，假设a1已经排序。否则，只需overlap (_, b1) (a2,_) = (b1>a2) && (a1<a2)。 - ssm针对线段问题的标准方法是按起点排序，然后从第一个开始走到最后。 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)
}
bitsSoFar = 0
for (n=0; n < bitPatterns.length; n++)
if (bitPatterns[n] & bitsSoFar != 0)
// overlap of bitPatterns[n] with an earlier pattern
bitsSoFar |= bitPatterns[n]
作为一项练习：
修改算法以识别位模式与后面的模式重叠
在O(1)时间内找出区间的比特模式
[ 10, 20] overlaps with [ 1, 100]
[ 30, 50] overlaps with [ 1, 100]
Resulting intervals that overlap with at least one other interval:
[ 1, 100]
[ 30, 50]
[ 10, 20]
(1, 100) 被计算两次，我使用了一个 Java 的 Set 来仅保留唯一的区间对象。O(N lg N)。intervalWithLatestEnd，即具有最新结束点的区间。intervalWithLatestEnd 重叠，则将它们都添加到 Set 中。必要时更新 intervalWithLatestEnd。此步骤为 O(N)。O(N lg N)。它需要一个大小为 O(N) 的输出 Set。
equals() 方法，如预期所示。class Interval {
int start;
int end;
Interval(int s, int e) {
start = s; end = e;
}
@Override
public String toString() {
return String.format("[%3d, %3d]", start, end);
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + start;
result = prime * result + end;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final Interval other = (Interval) obj;
if (start != other.start)
return false;
if (end != other.end)
return false;
return true;
}
}
以下是运行该算法的代码：
private static List<Interval> findIntervalsThatOverlap(List<Interval> intervals) {
// Keeps unique intervals.
Set<Interval> set = new HashSet<Interval>();
// Sort the intervals by starting time.
Collections.sort(intervals, (x, y) -> Integer.compare(x.start, y.start));
// Keep track of the interval that has the latest end time.
Interval intervalWithLatestEnd = null;
for (Interval interval : intervals) {
if (intervalWithLatestEnd != null &&
interval.start < intervalWithLatestEnd.end) {
// Overlap occurred.
// Add the current interval and the interval it overlapped with.
set.add(interval);
set.add(intervalWithLatestEnd);
System.out.println(interval + " overlaps with " +
intervalWithLatestEnd);
}
// Update the interval with latest end.
if (intervalWithLatestEnd == null ||
intervalWithLatestEnd.end < interval.end) {
intervalWithLatestEnd = interval;
}
}
// Convert the Set to a List.
return new ArrayList<Interval>(set);
}
以下是一个测试用例，运行原始的间隔：
public static void testcase() {
List<Interval> intervals = null;
List<Interval> result = null;
intervals = new ArrayList<Interval>();
intervals.add(new Interval(1, 3));
intervals.add(new Interval(12, 14));
intervals.add(new Interval(2, 4));
intervals.add(new Interval(13, 15));
intervals.add(new Interval(5, 10));
result = findIntervalsThatOverlap(intervals);
System.out.println("Intervals that overlap with at least one other interval:");
for (Interval interval : result) {
System.out.println(interval);
}
}
得到以下结果：
[ 2, 4] overlaps with [ 1, 3]
[ 13, 15] overlaps with [ 12, 14]
Intervals that overlap with at least one other interval:
[ 2, 4]
[ 1, 3]
[ 13, 15]
[ 12, 14]
最后，这是一个更高级的测试案例：
public static void testcase() {
List<Interval> intervals = null;
List<Interval> result = null;
intervals = new ArrayList<Interval>();
intervals.add(new Interval(1, 4));
intervals.add(new Interval(2, 3));
intervals.add(new Interval(5, 7));
intervals.add(new Interval(10, 20));
intervals.add(new Interval(15, 22));
intervals.add(new Interval(9, 11));
intervals.add(new Interval(8, 25));
intervals.add(new Interval(50, 100));
intervals.add(new Interval(60, 70));
intervals.add(new Interval(80, 90));
result = findIntervalsThatOverlap(intervals);
System.out.println("Intervals that overlap with at least one other interval:");
for (Interval interval : result) {
System.out.println(interval);
}
}
结果如下：
[ 2, 3] overlaps with [ 1, 4]
[ 9, 11] overlaps with [ 8, 25]
[ 10, 20] overlaps with [ 8, 25]
[ 15, 22] overlaps with [ 8, 25]
[ 60, 70] overlaps with [ 50, 100]
[ 80, 90] overlaps with [ 50, 100]
Intervals that overlap with at least one other interval:
[ 2, 3]
[ 8, 25]
[ 9, 11]
[ 50, 100]
[ 1, 4]
[ 15, 22]
[ 10, 20]
[ 60, 70]
[ 80, 90]
我已经有一段时间没有使用过它了，但我使用的解决方案是《算法导论》中描述的红黑树的一个变体，叫做区间树。它是按区间开始排序的树，因此您可以快速（二分搜索）找到第一个符合条件的节点。如果我没记错的话，这些节点是按某个属性排序的，当候选节点无法匹配您的区间时，该属性让您停止“遍历”整棵树。所以我认为它是O(m)搜索，其中m是匹配区间的数量。
我在搜索中发现了这个实现。
Brett
[编辑] 重新阅读问题，这不是你要求的。我认为当您已经有一份已排定会议列表（添加到树中）并且希望查找哪些会议室仍然可用于新的开始和持续时间的会议（搜索条件）时，这是最佳实现。希望这个解决方案还有一些相关性。
这个问题可以简化为元素唯一性问题。
元素唯一性具有Ω(n log n)的下限（计算比较次数），因此你无法做得比这更好。
你可以遍历列表一次，并保留一个哈希表来存储到目前为止遇到的所有区间。如果输入区间是哈希表中某个区间的一部分，则将其合并到哈希表区间中。标记非基本区间（由多个区间组成的合并区间）。
然后，您再次遍历列表，并针对每个区间在哈希表中检查它是否包含在合并的区间中。
我不知道它是否是O(N)，但它比O(N^2)要好得多。