leetcode56合并区间

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

type IntervalSlice [][]int

func (s IntervalSlice) Len() int { return len(s) }
func (s IntervalSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s IntervalSlice) Less(i, j int) bool { return s[i][0] < s[j][0] }

func merge(intervals [][]int) [][]int {
    if len(intervals) == 0 {
        return nil
    }
    sort.Sort(IntervalSlice(intervals))
    ans := make([][]int, 0, len(intervals))
    start := intervals[0][0]
    end := intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        e := intervals[i]
        if end >= e[0]  {
            if end <= e[1] {
                end = e[1]
            }
            
        } else {
            ans = append(ans, []int{start, end})
            start = e[0]
            end = e[1]
        }
    }
    ans = append(ans, []int{start, end})
    return ans
}