乐趣区

关于go:Leetcode专题56合并区间

LeetCode 链接:
https://leetcode.cn/problems/merge-intervals/description/
解题思路:
思路
prev 初始为第一个区间,cur 示意以后的区间,res 示意后果数组

开启遍历,尝试合并 prev 和 cur,合并后更新到 prev
合并后的新区间还可能和前面的区间重合,持续尝试合并新的 cur,更新给 prev
直到不能合并 —— prev[1] < cur[0],此时将 prev 区间推入 res 数组
合并的策略
原则上要更新 prev[0]和 prev[1],即左右端:
prev[0] = min(prev[0], cur[0])
prev[1] = max(prev[1], cur[1])
但如果先按区间的左端排升序,就能保障 prev[0] < cur[0]
所以合并只需这条:prev[1] = max(prev[1], cur[1])

func merge(intervals [][]int) [][]int {sort.Slice(intervals, func(i, j int) bool {return intervals[i][0] < intervals[j][0]
    })
    res := [][]int{}
    prev := intervals[0]

    for i := 1; i < len(intervals); i++ {cur := intervals[i]
        if prev[1] < cur[0] { // 没有一点重合
            res = append(res, prev)
            prev = cur
        } else { // 有重合
            prev[1] = max(prev[1], cur[1])
        }
    }
    res = append(res, prev)
    return res
}

func max(a, b int) int {if a > b { return a}
    return b
}
退出移动版