leetcode 56. 合并区间

题目描述

给出一个区间的集合,请合并所有重叠的区间。

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

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

题解

首先按照开始区间进行升序排序,然后遍历数组,得到最大的重叠区间

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func merge(intervals [][]int) [][]int {
n := len(intervals)
if n == 0 {
return intervals
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
s, e := intervals[0][0], intervals[0][1]
for i := 1; i < n; i++ {
if intervals[i][0] <= e && intervals[i][1] > e {
e = intervals[i][1]
} else if intervals[i][0] > e {
intervals = append(intervals, []int{s, e})
s, e = intervals[i][0], intervals[i][1]
}
}
intervals = append(intervals, []int{s, e})
return intervals[n:]
}