题解 | #牛舍扩建#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param intervals int整型二维数组
     * @param new_interval int整型一维数组
     * @return int整型二维数组
     */
    public int[][] insertNewInterval (int[][] intervals, int[] new_interval) {
        int start = intervals[0][0];
        int end = intervals[0][1];
        LinkedList<int[]> linkedList = new LinkedList<>();
        int index = 0;
        boolean flag = false;
        while (index < intervals.length) {
            if (end < new_interval[0]) {
                linkedList.add(new int[] {start, end});
                index++;
                if (index >= intervals.length) {
                    break;
                }
                start = intervals[index][0];
                end = intervals[index][1];
            } else {
                end = Math.max(end, new_interval[1]);
                start = Math.min(start, new_interval[0]);
                flag = true;
                index++;
                break;
            }
        }

        if (!flag) {
            linkedList.add(new int[] {new_interval[0], new_interval[1]});
        } else {
            for (int i = index; i < intervals.length; i++) {
                if (end < intervals[i][0]) {
                    linkedList.add(new int[] {start, end});
                    start = intervals[i][0];
                    end = intervals[i][1];
                } else {
                    end = Math.max(end, intervals[i][1]);
                }
            } 
            linkedList.add(new int[] {start, end});
        }
       
        int[][] arr = new int[linkedList.size()][];
        for (int i = 0; i < linkedList.size(); i++) {
            arr[i] = linkedList.get(i);
        }
        return arr;
    }

}

本题我采用的双指针来解决此题，所用编程语言是java。

我们可以把此题看做数组合并，可以将start初始为第一个数组的第一个元素，end为第一个数组的第二个元素，然后与插入的新数组元素进行比较

如果end小于新数组的第一个元素，start改变为下一个数组的第一个元素，end为下一个数组的第二个元素。

如果end大于等于新数组的第一个元素，end改变为end和新数组第二个元素的最大值，start改变为start和新数组第一个元素的最小，同时数组下标加一，新数组合并的标志设置为true.

新数组合并的标志为true之后，继续开始数组合并.

新数组合并的标志为false，则直接将新数组添加到原数组之后