class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res=new ArrayList<>();
        int n=intervals.length,cur=0;
        while(cur<n && intervals[cur][1] < newInterval[0]){
            res.add(intervals[cur++]);
        }
        while(cur<n && intervals[cur][0] <=newInterval[1]){
            newInterval[0]=Math.min(newInterval[0],intervals[cur][0]);
            newInterval[1]=Math.max(newInterval[1],intervals[cur][1]);
            ++cur;
        }
        res.add(newInterval);
        while(cur<n){
            res.add(intervals[cur++]);
        }
        return res.toArray(new int[0][]);
    }
}
code2:
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res=new ArrayList<>();
        int n=intervals.length,cur=0,temp=0;
        for(int i=0;i<n;i++){
            if(intervals[i][1] < newInterval[0]){
                res.add(intervals[i]);
                cur++;
            }else if(intervals[i][0] >newInterval[1]){
                if(temp==0){
                    res.add(newInterval);
                    temp--;
                }
                res.add(intervals[i]);
            }else{
                newInterval[0]=Math.min(newInterval[0],intervals[i][0]);
                newInterval[1]=Math.max(newInterval[1],intervals[i][1]);
            }
          
        }
         if(cur==n )
                res.add(newInterval);
        return res.toArray(new int[0][]);
    }
}