题解 | #牛舍扩建#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param intervals int整型二维数组 
     * @param new_interval int整型一维数组 
     * @return int整型二维数组
     */
    public int[][] insertNewInterval (int[][] intervals, int[] new_interval) {
        Arrays.sort(intervals,new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                return o1[0] - o2[0] ; 
            } ; 
        }) ;
        int l = 0 ; 
        int r = intervals.length-1 ;
        while(l <= r){
            int mid = (l+r)/2 ; 
            if(new_interval[0] < intervals[mid][0]){
                r = mid-1 ; 
            }else{
                l = mid+1 ; 
            }
        } 
        int st = 0 ; 
        int[][] newIntervals;
        if(r >= 0 && intervals[r][1] >= new_interval[0]){
            st = r ; 
            intervals[r][1] = Math.max(new_interval[1],intervals[r][1]) ; 
            newIntervals = intervals ; 
        }else{
            newIntervals = new int[intervals.length+1][] ; 
            if(r+1 > 0){
                System.arraycopy(intervals,0,newIntervals,0,r+1); 
            }
            if(r+1 < intervals.length){
                System.arraycopy(intervals,r+1,newIntervals,r+2,intervals.length-(r+1)) ;
            }
            newIntervals[r+1] = new_interval ; 
            st = r+1 ; 
        }
        int j = st+1 ; 
        while(j < newIntervals.length){
            if(newIntervals[st][1] >= newIntervals[j][0]){
                if(newIntervals[st][1] < newIntervals[j][1]){
                    newIntervals[st][1] = newIntervals[j][1] ; 
                    j++ ; 
                    break; 
                }else{
                    j++ ; 
                }
            }else{
                break ; 
            }
        }
        int[][] ans = new int[st+1+newIntervals.length-j][] ; 
        System.arraycopy(newIntervals,0,ans,0,st+1) ;
        System.arraycopy(newIntervals,j,ans,st+1,newIntervals.length-j) ;
         
        // write code here
        return ans ; 
    }
}

二分找到对应的数组位置,放入后和后面的interval进行合并