刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/merge-intervals/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

以数组 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 <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

思路

这道题其实不算特别难，暴力方法比较容易想到，直接一个个比对是否有交集，求并集即可，不过这样复杂度比较高，来尝试优化下吧。

如何优化，暴力法写出来应该是一个触目惊心的双层循环。那就先从这个for循环搞起。
思路过程：

• 想优化双层循环，那就要知道为什么需要双层循环：因为不确定每个已经加入结果集的区间，与新加入的区间是否有交集
• 那么有没有办法能够提前确定一部分结果集是否跟新区间有交集
• 类比随机搜索，如果数组本身有序，那就可以二分等等更快的搜索方式
• 那么，提供的区间集能否有序？以何种规则排序?
• 可以排序，以单边排序，按区间左边界排序，那就从左往右遍历合并，因为有序故只需要考虑右边界。翻过来按区间右边界排序同理。
• 到了这里应该没什么问题了，不过建议一般情况下就再多想一步：排序是否会对结果有影响？

代码

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    res := make([][]int, 0)
    // 题目条件确保数组不为空
    res = append(res, intervals[0])
    for i:=1; i < len(intervals); i++ {
        // 新加入的左边界一定比结果集最后一个左边界更大
        // 所以只需要看跟右边界的关系
        if intervals[i][0] > res[len(res)-1][1] {
            res = append(res, intervals[i])
        } else if intervals[i][1] > res[len(res)-1][1] {
        // 不一定更新右边界，因为可能是个当前最后一个结果区间的子区间
            res[len(res)-1][1] = intervals[i][1]
        }
    }
    return res
}