1
2
3

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

1
2
3

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func merge(intervals [][]int) [][]int {
	var res [][]int
	tmp := make([][]int, len(intervals))
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	i := 0
	for k, v := range intervals {
		if k == 0 {
			tmp[k] = v
		} else {
			if v[0] <= tmp[k-i-1][1] {
				if v[1] >= tmp[k-i-1][1] {
					tmp[k-i-1][1] = v[1]
				}
				i++
			} else {
				tmp[k-i] = v
			}
		}
	}
	for _, v := range tmp {
		if v != nil {
			res = append(res, v)
		}
	}
	return res
}