56. 合并区间

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

二，思路：

1. 根据示例将二维数组按照左侧值的大小，从小到大排列
2. 使用一个temp来记录合并后的数组大小
3. 比较两个数组，如：[1,3]，[2,6]。当3 > 2且肯定1<=2的，此时合并的数组是左侧最小值1，右侧3,6中最大值6即为[1,6]
4. 反向判断，是否2 > 3来得出，如果此时大于，说明temp已经是一个完整好了的合并区间，加入最终res[][] [] []中，并对temp重新赋值。
5. 如果小于登录，此时temp的右值temp[1]是此时temp[1]和比较的intervals[1] [1]中最大的值。更新temp。

三，代码

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {     // 按照左端点从小到大排序
        return intervals[i][0] < intervals[j][0]
    }) 
    res := make([][]int, 0, len(intervals))
    temp := intervals[0];
    for i:=1; i<len(intervals); i++{
        if temp[1] < intervals[i][0]{
            res = append(res,temp);
            temp = intervals[i];
        }else{
            temp[1] = max(intervals[i][1],temp[1])
        }
    }
    res = append(res,temp);
    return res;
}