【中等】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] 可被视为重叠区间。

用例3
intervals =[[1,4],[0,1]]
输出
[[0,1]]

提示：
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

解题

题目没提、示例没举，所以没考虑逆序情况。实际真得考虑的。
还在用冒泡，嘤嘤嘤。
看了题解：自己的解法真原始且幼稚

func merge(intervals [][]int) [][]int {

    result := [][]int{}
    s := make([]int, 2)

    for i:=0 ; i < len(intervals); i++{
        for j:=i+1 ; j < len(intervals); j++{
            if intervals[i][0] > intervals[j][0]{
                intervals[i], intervals[j] = intervals[j], intervals[i]
            }
        }
    }

    s = intervals[0]
    for _, v := range intervals{
        if v[0]<=s[1]{
            if v[0]<s[0]{
                s[0] = v[0]
            }
            if v[1] > s[1]{
                s[1] = v[1]
            }
        } else {
            result = append(result, s)
            s = v
        }
    }
    result = append(result, s)

    return result
}

题解

方法一：

1

func merge(intervals [][]int) (ans [][]int) {
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	ans = append(ans, intervals[0])
	for _, e := range intervals[1:] {
		if ans[len(ans)-1][1] < e[0] {
			ans = append(ans, e)
		} else {
			ans[len(ans)-1][1] = max(ans[len(ans)-1][1], e[1])
		}
	}
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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

时间：O(nlogn)
空间：O(logn)

长进

1. 排序都得顺一遍
2. 最新版本go中 新增了max方法