题解 | #牛舍扩建#

知识点：贪心 递归

思路：在上一题里加入一个数组就行了

编程语言：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
        ArrayList<int[]> array = new ArrayList<>();
        int [][]intervalss = new int[intervals.length + 1][2];
        for (int i=0;i<intervals.length;i++)
            intervalss[i] = intervals[i];
        intervalss[intervalss.length-1] = new_interval;
        //排序一下，之前的思路都是基于数组中第一个元素从小到大的排序
        Arrays.sort(intervalss, (int[] a, int[] b) -> (a[0] - b[0]));
        int left=intervalss[0][0],right=intervalss[0][1];//左右边界
        for (int i = 1;i<intervalss.length;i++){
            //取出数组
            if(right >=intervalss[i][0]){
                //更新子问题最优解
                //left = intervals[i][0];
                right = Math.max(intervalss[i][1],right);
            }else{
                array.add(new int[]{left,right});
                left = intervalss[i][0];
                right = Math.max(intervalss[i][1],right);
            }
        }
        array.add(new int[]{left,right});
        return array.toArray(new int[0][]);
    }
}