题解 | #牛舍扩建#

知识点：数组，双指针

对于新加入的区间，我们并不知道到底该插入到哪个位置，故我们可以先对所有的区间按左端点进行排序，我们还需要用到双指针的思想，左指针一定是指向左端点，对于右指针，分以下两种情况：

1.若下一个区间与当前区间有重合，我们需要判断是当前区间的右端点更大，还是下一个区间的右端点更大，以确保我们得到的是最大的区间。

2.若下一个区间与当前区间没有重合，则说明当前区间是不与任何区间相交的，则可以直接记录下来，作为一个不重复的区间。此时，我们需要重置左右端点。

最终得到的就是合并了新区间的不重叠区间

Java题解如下：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param intervals int整型二维数组 
     * @param new_interval int整型一维数组 
     * @return int整型二维数组
     */
    public int[][] insertNewInterval (int[][] intervals, int[] new_interval) {
        // write code here
        List<int[]> list = new ArrayList<>();
        for(int[] interval: intervals) {
            list.add(interval);
        }
        list.add(new_interval);
        Collections.sort(list, (o1, o2) -> (o1[0] - o2[0]));
        List<int[]> newList = new ArrayList<>();
        int left = list.get(0)[0], right = list.get(0)[1];
        for(int i = 1; i < list.size(); i++) {
            if(right >= list.get(i)[0]) {
                right = Math.max(right, list.get(i)[1]);
            }else {
                newList.add(new int[]{left, right});
                left = list.get(i)[0];
                right = list.get(i)[1];
            }
        }
        newList.add(new int[]{left, right});
        int[][] res = new int[newList.size()][2];
        for(int i = 0; i < newList.size(); i++) {
            res[i] = newList.get(i);
        }
        return res;
    }
}