57. 插入区间

题意：

解题思路：

思路：[3种可能性]：O(n)
1. 如果新区间的右端点要小于区间元素的左端点，则说明无重叠，先把新区间先加入数组；    
    1.1 intervals = [3,4], newInterval=[1,2] =》start = 3, end = 4
    1.2 arr = [1,2], start = 3, end = 4
2. 如果新区间的左端点数大于区间的右端点，则说明无重叠，先把区间数加入数组；
    2.1 intervals = [3,4], newInterval=[5,6] =》start= 5, end = 6
    2.2 arr = [3,4]
3. 如果跟新区间有相交,说明有重叠，则维护合并区间的最小左端点和最大右端点
    3.1 intervals = [[1,3]], newInterval = [2,5]
    3.2 arr = [1,5]

PHP代码实现：

class Solution {
    function insert($intervals, $newInterval) {
        $ret = [];
        $start = $newInterval[0];
        $end = $newInterval[1];
        foreach ($intervals as $interval) {
            if ($interval[0] > $end) {
                array_push($ret, [$start, $end]);
                $start = $interval[0];
                $end = $interval[1];
            }
            if ($interval[1] < $start || $interval[0] > $end) {
                array_push($ret, $interval);
            } else {
                $start = min($start, $interval[0]);
                $end = max($end, $interval[1]);
            }
        }
        array_push($ret, [$start, $end]);
        return $ret;
    }
}

GO代码实现：

func insert(intervals [][]int, newInterval []int) [][]int {
    res := [][]int{}
    start, end, n := newInterval[0], newInterval[1], len(intervals)
    for i := 0; i < n; i++ {
        if intervals[i][0] > end {
            res = append(res, []int{start, end})
            start = intervals[i][0]
            end = intervals[i][1]
        }
        if intervals[i][1] < start {
            res = append(res, intervals[i])
        } else {
            start = Min(intervals[i][0], start)
            end = Max(intervals[i][1], end)
        }
    }
    res = append(res, []int{start, end})
    return res
}
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
}