给出一个无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

 

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-interval

 

时间复杂度：O（n）

空间复杂度：O（1）

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        List<int []> resultList = new ArrayList<int []>();
        boolean addNewValue = false;
        for(int [] layer : intervals){
            //说明该层最大的值还要小于left值
            if(layer[1] < left){
                resultList.add(layer);
            } else if(layer[0] > right){
                //若是该层的最小值大于right
                //那么首先要把left和right放入到list中
                if(!addNewValue){
                    resultList.add(new int[]{left,right});
                    addNewValue = true;
                }
                //再把当前层放入list
                resultList.add(layer);
            } else {
                //比较left，right得到本层的最大值，最小值，再继续跟下一层对比
                left = Math.min(layer[0],left);
                right = Math.max(layer[1],right);
            }
        }
        //如果还没有把left和right放入到list中
        if(!addNewValue){
            resultList.add(new int[]{left,right});
        }
        int result[][] = new int [resultList.size()][2];
        for(int i = 0 ; i < resultList.size() ; i++){
            result[i][0] = resultList.get(i)[0];
            result[i][1] = resultList.get(i)[1];
        }
        return result;
    }
}