试题：合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]输出: [[1,5]]解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

--------------- 想一想？---------------

题解

方法 1：连通块

直觉

如果我们画一个图，区间看成顶点，相交的区间之间连一条无向边，那么图中连通块内的所有区间都可以合并成一个。

算法

根据上面的直觉，我们可以把图用邻接表表示，用两个方向的有向边模拟无向边。然后，为了考虑每个顶点属于哪个连通块，我们从任意一个未被访问的节点出发，遍历相邻点，直到所有顶点都被访问过。为了效率更快，我们将所有访问过的节点记录在 Set 中，可以在常数时间内查询和插入。最后，我们考虑每个连通块，将所有区间合并成一个新的 Interval ，区间左端点 start 是最小的左端点，区间右端点 end 是最大的右端点。

这个算法显然是正确的，因为这是最暴力的方法。我们对两两区间进行比较，所以可以知道他们是否重合。连通块搜索的原理是因为两个区间可能不是直接重合，而是通过第三个区间而间接重合。例如下面的例子(如图)，尽管区间 (1,5) 和 (6, 10) 没有直接重合，但是任意一个和 (4, 7) 合并之后就可以和另一个产生重合。图中有两个连通块，我们得到如下两个合并区间：(1, 10) 和 (15, 20)

class Solution: def overlap(self, a, b): return a.start <= b.end and b.start <= a.end # generate graph where there is an undirected edge between intervals u # and v iff u and v overlap. def build_graph(self, intervals): graph = collections.defaultdict(list) for i, interval_i in enumerate(intervals): for j in range(i+1, len(intervals)): if self.overlap(interval_i, intervals[j]): graph[interval_i].append(intervals[j]) graph[intervals[j]].append(interval_i) return graph # merges all of the nodes in this connected component into one interval. def merge_nodes(self, nodes): min_start = min(node.start for node in nodes) max_end = max(node.end for node in nodes) return Interval(min_start, max_end) # gets the connected components of the interval overlap graph. def get_components(self, graph, intervals): visited = set() comp_number = 0 nodes_in_comp = collections.defaultdict(list) def mark_component_dfs(start): stack = [start] while stack: node = stack.pop() if node not in visited: visited.add(node) nodes_in_comp[comp_number].append(node) stack.extend(graph[node]) # mark all nodes in the same connected component with the same integer. for interval in intervals: if interval not in visited: mark_component_dfs(interval) comp_number += 1 return nodes_in_comp, comp_number def merge(self, intervals): graph = self.build_graph(intervals) nodes_in_comp, number_of_comps = self.get_components(graph, intervals) # all intervals in each connected component must be merged. return [self.merge_nodes(nodes_in_comp[comp]) for comp in range(number_of_comps)]

复杂度分析

时间复杂度：O(n^2)

建图的时间开销 O(V + E) = O(V) + O(E) = O(n) + O(n^2) = O(n^2)，最坏情况所有区间都相互重合，遍历整个图有相同的开销，因为 visited 数组保证了每个节点只会被访问一次。最后每个节点都恰好属于一个连通块，所以合并的时间开销是 O(V) = O(n)O(V)=O(n)。总和为：O(n^2) + O(n^2) + O(n) = O(n^2)

空间复杂度：O(n^2)

根据之前提到的，最坏情况下每个区间都是相互重合的，所以两两区间都会有一条边，所以内存占用量是输入大小的平方级别。

方法 2：排序

直觉

如果我们按照区间的 start 大小排序，那么在这个排序的列表中可以合并的区间一定是连续的。

算法

首先，我们将列表按上述方式排序。然后，我们将第一个区间插入 merged 数组中，然后按顺序考虑之后的每个区间：如果当前区间的左端点在前一个区间的右端点之后，那么他们不会重合，我们可以直接将这个区间插入 merged 中；否则，他们重合，我们用当前区间的右端点更新前一个区间的右端点 end 如果前者数值比后者大的话。

一个简单的证明：假设算法在某些情况下没能合并两个本应合并的区间，那么说明存在这样的三元组 ii，jj 和 kk 以及区间 intsints 满足 i < j < ki<j<k 并且 (ints[i]ints[i], ints[k]ints[k]) 可以合并，而 (ints[i]ints[i], ints[j]ints[j]) 和 (ints[j]ints[j], ints[k]ints[k]) 不能合并。这说明满足下面的不等式：

ints[i].end<ints[j].start

ints[j].end<ints[k].start

ints[i].end≥ints[k].start

我们联立这些不等式（注意还有一个显然的不等式 ints[j].endints[j].start≤ints[j].end），可以发现冲突：

ints[i].end<ints[j].start≤ints[j].end<ints[k].start

ints[i].end≥ints[k].start

因此，所有能够合并的区间必然是连续的。

考虑上面的例子，当列表已经排好序，能够合并的区间构成了连通块。

class Solution: def merge(self, intervals): intervals.sort(key=lambda x: x.start) merged = [] for interval in intervals: # if the list of merged intervals is empty or if the current # interval does not overlap with the previous, simply append it. if not merged or merged[-1].end < interval.start: merged.append(interval) else: # otherwise, there is overlap, so we merge the current and previous # intervals. merged[-1].end = max(merged[-1].end, interval.end) return merged

复杂度分析

时间复杂度：O(nlogn)

除去 sort 的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 O(nlgn)

空间复杂度：O(1) (or O(n))

如果我们可以原地排序 intervals ，就不需要额外的存储空间；否则，我们就需要一个线性大小的空间去存储 intervals 的备份，来完成排序过程。

来源：力扣（LeetCode）

链接：

​