试题地址：https://leetcode-cn.com/problems/merge-intervals/

试题思路:
1、只有一个区域时，直接返回
2、将区间以下界进行排序
3、利用3维数组进行dp，每次比较临近两个区间，注意最后一个区间
4、区间比较时，需要考虑第一个区间上界是大于第二个区间的下界还是上界
比如输入：[[1 3] [15 18] [2 6] [8 10] [2 9]]
[[[1 3] [2 6] [2 9] [8 10] [15 18]]
[[1 6] [2 10] [15 18]]
[[1 10] [15 18]]
[[1 10] [15 18]]]

试题代码：

package main

import (
    "fmt"
    "sort"
)

func main() {
    intervals := [][]int{
        {1, 3},
        {2, 6},
        {8, 10},
        {2, 9},
        {15, 18},
    }
    // intervals := [][]int{
    //     {1, 6},
    //     {4, 5},
    // }
    fmt.Println(merge(intervals))
}

//试题地址：https://leetcode-cn.com/problems/merge-intervals/
func merge(intervals [][]int) [][]int {
    if len(intervals) == 1 {
        return intervals
    }

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

    result = append(result, intervals)
    i := 0
    for {
        k := 0
        result = append(result, [][]int{})
        for j := 0; j < len(result[i])-1; j++ {
            result[i+1] = append(result[i+1], []int{})
            fmt.Println(result)
            if result[i][j][1] >= result[i][j+1][0] {
                if result[i][j][1] >= result[i][j+1][1] {
                    result[i+1][k] = append(result[i+1][k], result[i][j][0])
                    result[i+1][k] = append(result[i+1][k], result[i][j][1])
                } else {
                    result[i+1][k] = append(result[i+1][k], result[i][j][0])
                    result[i+1][k] = append(result[i+1][k], result[i][j+1][1])
                }
                j++
            } else {
                result[i+1][k] = append(result[i+1][k], result[i][j][0])
                result[i+1][k] = append(result[i+1][k], result[i][j][1])
            }
            k++
            if j == len(result[i])-2 {
                result[i+1] = append(result[i+1], []int{})
                result[i+1][k] = append(result[i+1][k], result[i][j+1][0])
                result[i+1][k] = append(result[i+1][k], result[i][j+1][1])
            }
        }
        fmt.Println(result)
        if len(result[i]) == len(result[i+1]) || len(result[i]) == 1 {
            break
        }
        i++
    }
    return result[i]
}

View Code