合并区间

1. 题目描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

2. 思路

1. 思路一
   • 现根据第一个元素的大小排序，这样子结果就是升序的区间
   • 遍历每个区间，如果这个区间和上个区间存在交集，那么取并集；否则直接入库

3. 实现

3.1. 栈

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        a := intervals[i]
        b := intervals[j]
        return a[0] < b[0]
    })

    stack := make([][]int, 0)
    for _, interval := range intervals {
        if len(stack) == 0 {
            stack = append(stack, interval)
        }else {
            top := stack[len(stack)-1]
            //区间没有交集
            if top[1] < interval[0] {
                stack = append(stack, interval)
            //区间有交集
            }else {
                top[1] = max(top[1], interval[1])
                top[0] = min(top[0],interval[0])
               
            }
        }
    }

    return stack
}

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

func min(a, b int) int {
    if a > b {
        return b
    }

    return a
}

4. 参考

• 56. 合并区间 - 力扣（LeetCode）