插入区间

给你一个 无重叠的 _，_按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

function insert(intervals: number[][], newInterval: number[]): number[][] {
    //分为三个区域来找，一是左边未覆盖，中间覆盖，右侧未覆盖
    const result = []
    let i=0
    let n=intervals.length 
 
    //左侧
    while(i<n && intervals[i][1]<newInterval[0]){
        result.push(intervals[i])
        i++
    }
    //当前起点大于 new 的终点的时候，必有重叠
    while(i<n && intervals[i][0] <= newInterval[1]){
        newInterval[0] = Math.min(intervals[i][0],newInterval[0])
        newInterval[1] = Math.max(intervals[i][1],newInterval[1])
        i++
    }
    result.push(newInterval)
 
 
    //右侧
    while(i<n){
        result.push(intervals[i])
        i++
    }
    return result
};