给出一个区间的集合，请合并所有重叠的区间。
示例 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] 可被视为重叠区间。
func merge(intervals [][]int) [][]int {
n := len(intervals)
sort.Slice(intervals, func(a, b int) bool {
return intervals[a][0] < intervals[b][0]
})
// 如果当前区间的左端点在前一个区间的右端点之后，那么他们不会重合，我们可以直接将这个区间插入 merged 中；
// 否则，他们重合，我们用当前区间的右端点更新前一个区间的右端点 end 如果前者数值比后者大的话。
for i := 0;i < n-1;i++ {
if intervals[i][1] >= intervals[i+1][0] {
if intervals[i+1][1] > intervals[i][1] {
intervals[i][1] = intervals[i+1][1]
}
// 向前合并
// [1,6], [2, 6] --> [1,6]
intervals = append(intervals[:i+1], intervals[i+2:]...)
i--
n--
}
}
return intervals
}
输入:
[[1,4],[5,6]]
输出
[[1,6]]
预期结果
[[1,4],[5,6]]
附赠错误代码
func merge(intervals [][]int) [][]int {
if len(intervals) == 0 {
return intervals
}
var split [][]int
var list []int
var res [][]int
//nums = [][]int{{1,3},{2,6},{8,10},{15,18}}
list = make([]int, intervals[len(intervals)-1][len(intervals[len(intervals)-1])-1]+2)
for _, v := range intervals {
min := v[0]
max := v[len(v)-1]
for i:=min; i<=max; i++ {
list[i] = i
}
}
//fmt.Println(list)
// [0 1 2 3 4 5 6 0 8 9 10 0 0 0 0 15 16 17 18 0]
var temp []int
for _, v := range list {
if v != 0 {
temp = append(temp, v)
} else {
if len(temp) != 0 {
split = append(split, temp)
}
temp = []int{}
}
}
// [[1 2 3 4 5 6] [8 9 10] [15 16 17 18]]
for _, v := range split {
res = append(res, []int{v[0], v[len(v)-1]})
}
return res
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a < b {
return b
}
return a
}