56. 合并区间

题目描述：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。

请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

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

示例 2：

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

提示：

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

---

解题分析及思路：

由于题目未标明intervals是有序的，所以我们首先需要保证intervals是有序的，这样方便我们后序进行操作。

因为可以合并的区间一定是连续的，而合并前若想将某两个区间进行合并，则需要将两个区间进行比较，为了避免无效比较，所以我们需要将intervals按照一定规则进行排序。

首先，我们将列表按照区间的左端点进行排序，左端点相同的情况下，按照右端点进行排序。

例如{1, 6}, {1, 5}, {0, 1}, {0, 6}, {0, 3}, {6, 9}，排序后为{0, 1}, {0, 3}, {0, 6}, {1, 5}, {1, 6}, {6, 9}。

然后，我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：

• 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
• 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。

func merge1(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] > intervals[j][0] {
			return false
		}
		if intervals[i][0] == intervals[j][0] && intervals[i][1] > intervals[j][1] {
			return false
		}
		return true
	})
	result := make([][]int, 0)
	result = append(result, intervals[0])
	for i := 1; i < len(intervals); i++ {
		left := result[len(result)-1]
		right := intervals[i]
		if left[1] < right[0] {
			result = append(result, right)
		} else if left[1] < right[1] {
			result[len(result)-1][1] = right[1]
		}
	}
	return result
}

复杂度：

• 时间复杂度：O(N*logN)，其中 N 为数组的长度，每个元素最多遍历一次。
• 空间复杂度：O(logN)，只使用常数额外空间。不考虑输入数组本身的空间占用。

执行结果：

• 执行耗时:21 ms,击败了17.08% 的Go用户
• 内存消耗:6.1 MB,击败了73.13% 的Go用户