题目: 插入区间

分析

二分法

按照 newInterval 的左值查找在区间的位置。

然后将该区间和该位置左右两侧的区间进行合并。

题解

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if(intervals==null||intervals.length==0){
            int[][] ans=new int[1][2];
            ans[0][0]=newInterval[0];
            ans[0][1]=newInterval[1];
            return ans;
        } 
        ArrayList<int[]> res=new ArrayList<>();
        boolean flag=false;
        for(int[] temp:intervals){
            if(newInterval[0]>temp[1]){
                res.add(temp);
            }else if(temp[0]>newInterval[1]){
                if(!flag){
                    res.add(newInterval);
                    flag=true;
                }
                res.add(temp);
            }else{
                newInterval[0]=Math.min(newInterval[0],temp[0]);
                newInterval[1]=Math.max(newInterval[1],temp[1]);
            }
        }
        if(!flag){
            res.add(newInterval);
        }
        int[][] ans=new int[res.size()][2];
        for(int i=0;i<res.size();i++){
            ans[i][0]=res.get(i)[0];
            ans[i][1]=res.get(i)[1];
        }
        return ans;
    }
}