56. 合并区间

题意：

解题思路：

思路：
1. 先按首位置进行排序[intervals[i][0]];
2. 如何判断两个区间是否重叠 a = [1,3],b = [2,6]
3. 当 b[0] <= a[1], 2 < 3 说明两个区间有重叠.
4. 那么区间就是 [a[0], max(a[1], b[1])],所以区间为:[1,6]

PHP代码实现：

class Solution {
    function merge($intervals) {
        if (count($intervals) < 1) return [];
        $intervals = $this->arraySort($intervals);
        $j = 0;
        $ans[$j] = $intervals[0];
        for ($i = 1; $i < count($intervals); $i++) {
            $start = $intervals[$i][0];
            $end = $intervals[$i][1];
            if ($start <= $ans[$j][1]) {
                $ans[$j] = [$ans[$j][0], max($ans[$j][1], $end)];
            } else {
                $j++;
                $ans[$j] = $intervals[$i];
            }
        }
        return $ans;
    }
    function arraySort($intervals) {
        $startArray = [];
        foreach ($intervals as $interval) {
            $startArray[] = $interval[0];
        }
        array_multisort($startArray, SORT_ASC, $intervals);
        return $intervals;    
    }
}

GO代码实现：

func merge(intervals [][]int) [][]int {
    if len(intervals) <= 1 {
        return intervals
    }
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    res := make([][]int, 0)
    start := intervals[0][0]
    end := intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        if end < intervals[i][0] {
            res = append(res, []int{start, end})
            start = intervals[i][0]
            end = intervals[i][1]
        } else {
            end = max(end, intervals[i][1])
        }
    }
    res = append(res, []int{start, end})
    return res
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}