共计 721 个字符,预计需要花费 2 分钟才能阅读完成。
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
}
正文完