LeetCode-56.合并区间 - sheep44044的小站

数组#

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

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

示例 2：

1
输入：intervals = [[1,4],[4,5]]
2
输出：[[1,5]]
3
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例 3：

1
输入：intervals = [[4,7],[1,4]]
2
输出：[[1,7]]
3
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

第二次手撕

1
func merge(intervals [][]int) [][]int {
2
    if len(intervals) <= 1 {
3
        return intervals
4
    }
5

6
    sort.Slice(intervals, func(i, j int) bool {
7
        return intervals[i][0] < intervals[j][0]
8
    })
9

10
    res := [][]int{intervals[0]}
11
    for i := 1; i < len(intervals); i++ {
12
        if intervals[i][0] <= res[len(res)-1][1] {
13
            if intervals[i][1] > res[len(res)-1][1] {
14
                res[len(res)-1][1] = intervals[i][1]
15
            }
16
        }else {
17
            res = append(res, intervals[i])
18
        }
19
    }
20

21
    return res
22
}

看了思路后写的

思路：1.排序

2.遍历排序后的区间。

如果当前区间的左端点 ≤ 结果集中最后一个区间的右端点，说明有重叠，合并（更新结果集最后一个区间的右端点为两者的最大值）。
如果当前区间的左端点 > 结果集中最后一个区间的右端点，说明不重叠，直接作为新区间加入结果集

1
func merge(intervals [][]int) [][]int {
2
    if len(intervals) <= 1 {
3
        return intervals
4
    }
5

6
    sort.Slice(intervals,func(i, j int) bool {
7
        return intervals[i][0] < intervals[j][0]
8
    })
9

10
    res := [][]int{intervals[0]}
11
    for i := 1; i < len(intervals); i++ {
12
        current := intervals[i]
13
        last := &res[len(res)-1]
14

15
        if current[0] <= (*last)[1] {
16
            if current[1] > (*last)[1] {
17
                (*last)[1] = current[1]
18
            }
19
        }else{
20
                res = append(res, current)
21
            }
22

23
    }
24

25
    return res
26
}