56合并区间 go解题
这里解法是直接找一个快排模板，然后排序了第一个数，所以需要多加一个判断逻辑并且稍微覆盖。
package main
import "fmt"
func main() {
fmt.Println(merge([][]int{{0, 2}, {2, 3}, {4, 4}, {0, 1}, {5, 7}, {4, 5}, {0, 0}}))
// fmt.Println(merge([][]int{{2, 3}, {4, 5}, {6, 7}, {8, 9}, {1, 10}}))
// fmt.Println(merge([][]int{{1, 4}, {1, 5}, {0, 0}}))
}
func merge(intervals [][]int) [][]int {
if len(intervals) == 0 {
return intervals
}
quickSort(intervals, 0, len(intervals)-1)
res := make([][]int, 0)
res = append(res, intervals[0])
tmpmax := 0 // 可能有包含关系
for i := 1; i < len(intervals); i++ {
//快排时没有处理第二位数字，会有1,5;1,4这种错误交换
if intervals[i][0] == intervals[i-1][0] {
tmpmax = max(intervals[i][1], intervals[i-1][1])
// 并且暴力地把他们都用最大数覆盖了
intervals[i][1], intervals[i-1][1] = tmpmax, tmpmax
res[len(res)-1][1] = max(res[len(res)-1][1], tmpmax)
continue
}
if intervals[i][0] <= intervals[i-1][1] || res[len(res)-1][1] >= intervals[i][1] || res[len(res)-1][1] >= intervals[i][0] {
// 已经加入res的可能对后面独立区间有包含关系
tmpmax = max(intervals[i][1], intervals[i-1][1])
res[len(res)-1][1] = max(res[len(res)-1][1], tmpmax)
} else {
res = append(res, intervals[i])
}
}
return res
}
func quickSort(nums [][]int, l, r int) { //[l,r]
if l < r {
m := partition(nums, l, r)
quickSort(nums, l, m-1)
quickSort(nums, m+1, r)
}
}
func partition(nums [][]int, l int, r int) int {
key := nums[r][0]
i := l
j := l
for j < r {
if nums[j][0] < key {
nums[i][0], nums[j][0] = nums[j][0], nums[i][0]
nums[i][1], nums[j][1] = nums[j][1], nums[i][1]
i++
}
j++
}
nums[i][0], nums[r][0] = nums[r][0], nums[i][0]
nums[i][1], nums[r][1] = nums[r][1], nums[i][1]
return i
}
假如把第二个数一起排序了：
package main
import "fmt"
func main() {
// fmt.Println(merge([][]int{{0, 2}, {2, 3}, {4, 4}, {0, 1}, {5, 7}, {4, 5}, {0, 0}}))
// fmt.Println(merge([][]int{{2, 3}, {4, 5}, {6, 7}, {8, 9}, {1, 10}}))
fmt.Println(merge([][]int{{1, 10}, {2, 3}, {4, 5}}))
}
func merge(intervals [][]int) [][]int {
if len(intervals) == 0 {
return intervals
}
quickSort(intervals, 0, len(intervals)-1)
res := make([][]int, 0)
res = append(res, intervals[0])
tmpmax := 0 // 可能有包含关系
for i := 1; i < len(intervals); i++ {
// 如果上一个区间完全包含于res，最后一个res的可能对后面的“看似独立区间”有包含关系
// {1，10}，{2，3}，{4，5} // {1，10}，{2，3}，{4，15}
if intervals[i][0] <= intervals[i-1][1] || res[len(res)-1][1] >= intervals[i][1] || res[len(res)-1][1] >= intervals[i][0] {
tmpmax = max(intervals[i][1], intervals[i-1][1])
res[len(res)-1][1] = max(res[len(res)-1][1], tmpmax)
} else {
res = append(res, intervals[i])
}
}
return res
}
func quickSort(nums [][]int, l, r int) { //[l,r]
if l < r {
m := partition(nums, l, r)
quickSort(nums, l, m-1)
quickSort(nums, m+1, r)
}
}
func partition(nums [][]int, l int, r int) int {
key := nums[r][0]
i := l
j := l
for j < r {
// 第一个数相同时，第二数也要小才是真的小
if (nums[j][0] < key) || (nums[j][0] == key && nums[j][1] < nums[r][1]) {
nums[i][0], nums[j][0] = nums[j][0], nums[i][0]
nums[i][1], nums[j][1] = nums[j][1], nums[i][1]
i++
}
j++
}
nums[i][0], nums[r][0] = nums[r][0], nums[i][0]
nums[i][1], nums[r][1] = nums[r][1], nums[i][1]
return i
}