可能的采访问题：如何查找所有重叠间隔
这本身并不是一个面试问题，因为我在我的项目中遇到了这个问题，但我认为这可能是一个体面的问题。
你有N对间隔，整数。 你需要识别所有在O（N）时间内彼此重叠的区间。 例如，如果你有
{1,3} {12,14} {2,4} {13,15} {5,10}
答案是{1,3}，{12,14}，{2,4}，{13,15}。 请注意，您不需要对它们进行分组，因此结果可以按照任何顺序进行，如示例中所示。
我只是抛出O（N）时间，因为KMPalgorithm将O（N）用于stringsearch。 ：d
我想出的最好的和我现在在项目中使用的是O（N ^ 2）。 是的，蛮力是相当伤心的，但没有人抱怨，所以我不会重构它。 ：P仍然，我很好奇，如果一个更好的头脑有一个更优雅的解决scheme。
将间隔的端点放入一个数组中，将它们标记为开始点或结束点。 如果间隔closures，则通过在起始点之前放置端点来打断关系，或者如果半开放，则反过来对其进行sorting。
1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E 然后遍历列表，跟踪我们在多less间隔（这相当于处理的起始点的数量减去终点的数量）。 当我们已经在一个区间内时，每当我们开始点时，这意味着我们必须有重叠区间。
1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E ^ ^ overlap overlap
我们可以通过在端点旁边存储数据来find哪些区间重叠，并跟踪我们所处的区间。
这是一个O（N logN）解决scheme，sorting是主要因素。
按开始点sorting间隔。 然后折叠这个列表，如果它们重叠，则将它们的每个区间与它的邻居（即（1,4），（2,6） – >（1,6））合并。 结果列表包含那些没有重叠伙伴的间隔。 从原始列表中筛选出来。
在初始sorting操作之后，这可以用任何（n log n）algorithm完成。 不知道你会如何解决这个问题。 如果利用已经sorting好的第一个操作的input和输出的顺序，那么即使是最后的“过滤出重复”操作也是线性的。
这里是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)]
在线问题的标准方法是根据出发点进行sorting，然后从头到尾走路。 O(n*logn) （ O(n)如果已经sorting）
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) }
不知道O（N），但是如果我们首先按照每个元组中的第一个数字对它们进行sorting，然后依次find那些元组的第一个数字大于在前面元组中看到的最大数字的元素，不与下一个元组重叠。
所以你会首先得到：
{1,3}，{2,4}，{5,10}，{12,14}，{13,15}
自4（最大）<5和10 <12，{5,10}被隔离。
这需要我们跟踪我们遇到的最大数量，每当我们find一个起始数字更大的元组时，我们检查它是否与下一个重叠。
这取决于sortingalgorithm的效率，因为后一个过程将是O（N）
假设起点和终点之间的差异很小，比如说<32。 1..32。 然后每个间隔可以写成32位字的位模式。 例如[1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 。 如果它们的位AND不为零AND则两个间隔或间隔的组合重叠。 例如。 [1,2]重叠[1,3]因为001&011 == 001 ，非零。 O（n）alg是保持到目前为止所看到的间隔的运行按位OR，并且AND每个新的：
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]
留作练习：
-
修改algorithm以便还识别比特模式与较晚的比特模式的重叠
-
在O（1）中计算一个区间的位模式，
如果N对间隔是整数，那么我们可以得到O（n）。
按照对中的第一个数字和第二个数字对它进行sorting。 如果都是整数，我们可以用桶sorting或基数sorting来得到O（n）。
{1,3}，{2,4}，{5,10}，{12,14}，{13,15}
然后一个接一个地合并，
{1,3}
{1,4}重叠{1,3}和{2,4}
{1,4}，{5,10}
{1,4}，{5,10}，{12,14}
{1,4}，{5,10}，{12,15}重叠{12,14}和{13,15}
这个组合将花费O（N）时间
这个问题可以归结为元素唯一性问题。
元素唯一性具有欧米茄（n log n）下限（计数比较次数），所以你不能做得比这更好。
自从我使用它之后已经有一段时间了，但是我使用的解决scheme是“algorithm简介”中介绍的称为区间树的红黑树的衍生物。 它是按间隔开始sorting的树，所以您可以快速（二进制search）第一个合格的节点。 IIRC，节点是由一个属性sorting的，当候选节点不匹配您的时间间隔时，让您停止“漫游”树。 所以我认为是O（m）search，其中m是匹配间隔的数量。
我search发现这个实现 。
布雷特
重读这个问题，这不是你问的问题。 我认为这是最好的实施，当你有一个（例如）已经安排在会议室（已添加到树中）的会议列表，并且您想要查找哪个会议室仍然可用于新的开始和持续时间（search词）。 不过，希望这个解决scheme有一些相关性。
int find_no_overlapping_intervals(const vector< pair<int, int>& a) { // a[i].first -> X ,a[i].second->Y // sort by start time sort.begin(a.begin(), a.end()); // maintain <end-time, its frequency> in m map<int, int> m; // i // for each point, we know its a[i].X >= a[0].X. ....a[i-1].X // there will be overlap, if for some j < i, a[j].Y >= a[i].X // lower_bound to find this.. it can be found in O(log(n)) as we use std::map for maintaining y int ans = 0; for (int i=0; i < a.begin(); i++) { auto sit = m.lower_bound(m.begin(), m.end(), a[i].first); auto eit = m.upper_bound(m.begin(), m.end(), a[i].first); for (auto it = sit; it != eit; it++) ans += it->second; m[a[i].second]++; } return ans; }
public ArrayList<Interval> merge(ArrayList<Interval> intervals) { ArrayList<Interval> res = new ArrayList<Interval>(); if (intervals == null || intervals.isEmpty()) return res; Comparator<Interval> comparator = new Comparator<Interval>() { @Override public int compare(Interval i1, Interval i2) { if (i1.start < i2.start) return -1; else if (i1.start > i2.start) return 1; else { if (i1.end < i2.end) return -1; else if (i1.end > i2.end) return 1; else return 0; } } }; Collections.sort(intervals, comparator); for (int i = 0; i < intervals.size(); i++) { Interval cur = intervals.get(i); if (res.isEmpty()) { res.add(cur); } else { Interval last = res.get(res.size() - 1); if (last.end >= cur.start) { last.end = Math.max(last.end, cur.end); } else { res.add(cur); } } } return res; }
在Python中这是一个简单的O(N*log(N))实现：
def overlapping(intervals): last = (-1, -1) overlapping = set() for curr in sorted(intervals, key=lambda p: p[0]): if curr[0] < last[1]: overlapping.add(curr) overlapping.add(last) last = max(curr, last, key=lambda p: p[1]) return list(overlapping - set((-1, -1))) print overlapping([(1, 3), (12, 14), (2, 4), (13, 15), (5, 10)]) #=> [(1, 3), (13, 15), (2, 4), (12, 14)]
首先，通过结束时间来对间隔进行sorting，比每个间隔比较初始时间与发现的最大结束时间，如果较小，则意味着存在重叠。
sorting部分是需要最多时间的部分，所以最终的复杂度是N*log(N) 。
使用扫描线algorithm在C ++中实现（ O(N log N) ）：
#include <algorithm> #include <iostream> #include <set> #include <tuple> #include <vector> struct Interval { double start; double end; }; //----------------------------------------------------------------------------- // Enum to qualify event: Start/End of "segment-line" enum class EIntervalState { Start, End }; //----------------------------------------------------------------------------- // Events used for collision detection struct Event { double pos; EIntervalState state; std::size_t id; }; //----------------------------------------------------------------------------- // Comparator to use if {1, 2} and {2, 3} should overlap class LessIncludeLimit { public: bool operator()(const Event& lhs, const Event& rhs) const { return std::tie(lhs.pos, lhs.state) < std::tie(rhs.pos, rhs.state); } }; //----------------------------------------------------------------------------- // Comparator to use if {1, 2} and {2, 3} should not overlap class LessExcludeLimit { public: bool operator()(const Event& lhs, const Event& rhs) const { return std::tie(lhs.pos, rhs.state) < std::tie(rhs.pos, lhs.state); } }; //----------------------------------------------------------------------------- std::vector<Event> MakeEvents(const std::vector<Interval>& intervals) { std::vector<Event> res; std::size_t id = 0; for (const auto& interval : intervals) { res.push_back({interval.start, EIntervalState::Start, id}); res.push_back({interval.end, EIntervalState::End, id}); ++id; } return res; } //----------------------------------------------------------------------------- template <typename Less> std::vector<std::pair<std::size_t, std::size_t>> ComputeOverlappingIntervals(std::vector<Event>&& events, Less less) { std::sort(events.begin(), events.end(), less); std::set<std::size_t> activeIds; std::vector<std::pair<std::size_t, std::size_t>> res; for (const auto& event : events) { switch (event.state) { case EIntervalState::Start: { for (const auto& id : activeIds) { res.emplace_back(std::minmax(event.id, id)); } activeIds.emplace(event.id); break; } case EIntervalState::End: { activeIds.erase(event.id); break; } } } return res; }
并使用它：
int main() { const std::vector<Interval> intervals = { {1, 3}, {12, 14}, {2, 4}, {13, 15}, {5, 10} }; for (const auto& p : ComputeOverlappingIntervals(MakeEvents(intervals), LessExcludeLimit{})) { std::cout << "intervals " << p.first << " and " << p.second << " overlap\n"; } }
演示
你可以遍历一次列表，并保存迄今为止遇到的所有间隔的散列表。 如果input时间间隔是来自哈希表的某个时间间隔的一部分，则将其合并到哈希表间隔中。 标记非原始间隔（由多个间隔组成的合并间隔）。
然后再次检查列表，并在每个时间间隔内检查哈希表是否包含在合并间隔中。
我不知道是不是O（N），但是比O（N ^ 2）好多了。
