题目描述#

给定一个区间数组 intervals，其中 intervals[i] = [starti, endi] 表示一个闭区间。

需要把所有有重叠部分的区间合并起来，最终返回一个互不重叠、并且恰好覆盖原始所有区间的结果数组。

知识边界#

排序后线性合并#

这题的关键不在于暴力比较每一对区间，而是先按左端点排序。排完序之后，后面的区间只需要和当前已经合并好的最后一个区间比较，就能决定是继续合并，还是直接开启一个新区间。

如果当前区间 p 的左端点 p[0] 小于等于结果数组最后一个区间的右端点，说明它们有重叠，此时只需要更新右端点，把它扩成两者右端点的较大值。

如果当前区间的左端点已经大于最后一个区间的右端点，说明它和前面的区间完全分开，就应该直接作为一个新区间加入答案。

这种写法依赖一个前提：排序后，所有可能与当前区间重叠的候选区间，一定已经被处理过并压缩到了 ans 的最后一个位置。所以不需要回头找，也不需要多层循环。

思路#

先按每个区间的起点从小到大排序。排序完成后，从左到右遍历所有区间。

遍历到一个新区间时，先看答案数组是否为空；如果为空，直接加入。否则只需要比较它和答案数组最后一个区间是否重叠。若重叠，就更新最后一个区间的右端点；若不重叠，就把当前区间追加进去。

这样每个区间只会被遍历一次，排序花费 O(n log n)，扫描合并花费 O(n)，所以总时间复杂度是 O(n log n)。额外空间主要来自结果数组；排序如果不计内部实现带来的开销，扫描部分只使用常量级变量。

代码#

import "slices"

func merge(intervals [][]int) (ans [][]int) {
	slices.SortFunc(intervals, func(p, q []int) int {
		return p[0] - q[0]
	})
	for _, p := range intervals {
		m := len(ans)
		if m > 0 && p[0] <= ans[m-1][1] {
			ans[m-1][1] = max(ans[m-1][1], p[1])
		} else {
			ans = append(ans, p)
		}
	}
	return
}