1、前言

2、思路

这其实是借助56题合并区间的解法，首先将新区间加入结果集，然后再合并区间。加入的过程中与每一个数组最左端比较，但是有可能数组没加入成功，那么还要与最后一个的最左端比较，如果大于再加入到最后，形成一个左端递增的数组。

3、代码

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if(intervals == null || intervals.length == 0){
            return new int[][]{newInterval};
        }

       // 数组左端递增
        int n = intervals.length;
        List<int[]> list = Arrays.stream(intervals).collect(Collectors.toList());
        for (int i = 0; i < n; i++) {
            if(newInterval[0] <= list.get(i)[0]){
                list.add(i, newInterval);
            }
        }
        if(newInterval[0] >= list.get(list.size() - 1)[0]){
            list.add(newInterval);
        }

        List<int[]> result = new ArrayList<>();
        result.add(list.get(0));
        for (int i = 1; i < list.size(); i++) {
            int[] temp = result.get(result.size() - 1);
            int[] interval = list.get(i);
            if(temp[1] < interval[0]){
                result.add(interval);
            }else {
                temp[1] = Math.max(temp[1], interval[1]);
            }
        }
        
        return result.toArray(new int[][]{});
    }
}