57. Insert Interval

T: O(n)

S: O(n)

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        int n = intervals.length;
        int i = 0;
        while (i < n && intervals[i][1] < newInterval[0]) {
            res.add(intervals[i]);
            i++;
        }
        int s = newInterval[0];
        int e = newInterval[1];
        while (i < n && intervals[i][0] <= e) {
            s = Math.min(intervals[i][0], s);
            e = Math.max(intervals[i][1], e);
            i++;
        }
        res.add(new int[]{s, e});
        
        while (i < n) {
            res.add(intervals[i]);
            i++;
        }
        
        int[][] result = new int[res.size()][2];
        for (int r = 0 ; r < res.size(); r++) {
            result[r] = res.get(r);
        }
        return result;
    }
}

/*
intervals is sorted in ascending 


[1,3],   [6,9]
   [2,5]
   
[[1,2],[3,5],[6,7],[8,10],[12,16]]
         [4,          9]
         
         1. add no intersection intervals
         
         2.
         when new[end] >= each interval[s]
         how to merge?
         find min in these intervals & new intervals
              max
         => [3,5],[6,7],[8,10], [4, 9], min is 3, max is 10 => [3, 10]
         
         3.
         add remain intervals
*/