LeetCode 56. 合并区间

LeetCode 56. 合并区间
 
以数组 intervals表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 
示例 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 <= 104

思路：

每次循环时，对前后两个区间的左右区间分别进行判断。

• 先对 intervals 所有子数组的左边界升序排序，避免出现无序的 intervals 数组，例如：[[1,4],[0,4]]，导致输出错误结果：[1,4]而非[0,4]

• 然后开始合并：

  • 若前一个区间右边界 > 后一个区间左边界，则可开始合并。

  注意需要将前一个区间的右边界 preRight 分别于后一个区间的左右边界 endLeft，endRight 进行比较，避免漏掉某些情况

  • 若前一个区间右边界 < 后一个区间左边界，则无法合并，直接追加【前一个区间】到res中
• res = append(res, intervals[len(intervals)-1]) ：追加 intervals 的最后一个元素到 res 结果集中：因为之前每次append的是前一个区间 res = append(res, intervals[i-1])，导致 intervals 的最后一个区间被漏掉

时间复杂度：

O(nlogn)，其中 n 为区间的数量。除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 O(nlog⁡n)。

空间复杂度：

O(logn)，其中 n 为区间的数量。这里计算的是存储答案之外，使用的额外空间。O(log⁡n) 即为排序所需要的空间复杂度。

详情见注释：

func merge(intervals [][]int) [][]int {
    // 升序排序：避免出现无序的intervals数组，例如：[[1,4],[0,4]]，导致输出错误结果：[1,4]而非[0,4]
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    res := make([][]int, 0)
    for i := 1; i < len(intervals); i++ {
        preLeft, preRight := intervals[i-1][0], intervals[i-1][1]
        endLeft, endRight := intervals[i][0], intervals[i][1]

        // 若前一个区间右边界 > 后一个区间左边界，则可开始合并
        if preRight >= endLeft { 
            if preRight >= endRight {
                intervals[i] = []int{preLeft, preRight}
            } else {
                intervals[i] = []int{preLeft, endRight}
            }

        // 若前一个区间右边界 < 后一个区间左边界，则无法合并，直接追加【前一个区间】到res中
        } else {
            // res = append(res, intervals[i-1])
            res = append(res, []int{preLeft, preRight})
        }
    }

    // 追加intervals的最后一个元素：因为之前每次append的是前一个区间，导致intervals的最后一个区间被漏掉
    res = append(res, intervals[len(intervals)-1]) 

    return res
}