mirror of
https://github.com/cubixle/codekata-golang.git
synced 2026-04-24 21:24:46 +01:00
67 lines
1.2 KiB
Go
67 lines
1.2 KiB
Go
package main
|
||
|
||
import (
|
||
"sort"
|
||
)
|
||
|
||
//56. 合并区间
|
||
//
|
||
//给出一个区间的集合，请合并所有重叠的区间。
|
||
//
|
||
//
|
||
//示例 1:
|
||
//
|
||
//输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
|
||
//输出: [[1,6],[8,10],[15,18]]
|
||
//解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
|
||
//示例 2:
|
||
//
|
||
//输入: intervals = [[1,4],[4,5]]
|
||
//输出: [[1,5]]
|
||
//解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
|
||
//注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
|
||
//
|
||
//提示：
|
||
//intervals[i][0] <= intervals[i][1]
|
||
|
||
func main() {
|
||
|
||
}
|
||
|
||
func mergeAndSortSlices(src [][]int) []int {
|
||
var ret []int
|
||
for _, s := range src {
|
||
for _, n := range s {
|
||
ret = append(ret, n)
|
||
}
|
||
}
|
||
sort.Ints(ret)
|
||
return ret
|
||
}
|
||
|
||
func pickInterval(src []int) [][]int {
|
||
left := 0
|
||
i := 1
|
||
var ret [][]int
|
||
for {
|
||
if i+1 > len(src)-1 {
|
||
if left < len(src) {
|
||
ret = append(ret, [][]int{{src[left], src[i]}}...)
|
||
}
|
||
break
|
||
}
|
||
if src[i]+1 < src[i+1] {
|
||
ret = append(ret, [][]int{{src[left], src[i+1]}}...)
|
||
i += 2
|
||
left = i
|
||
continue
|
||
}
|
||
i++
|
||
}
|
||
return ret
|
||
}
|
||
|
||
func merge(src [][]int) [][]int {
|
||
return pickInterval(mergeAndSortSlices(src))
|
||
}
|