Cacher is the code snippet organizer for pro developers

/*
Note:
1. ⭐️代表newInterval之后的interval
    if(newInterval == null || interval[1] < newInterval[0]) 中的 newInterval == null
2. ⭐️可能newInterval存在在最后一段
    if(newInterval != null) 
      res.add(newInterval);


Explanation:
___: current interval(i); _ _ _: newInterval

1) i.end < newInterval.start，then we can safely add i to result;
	newInterval still needs to be compared with latter intervals
	|________|
			       |_ _ _ _ _|
			
2) i.start > newInterval.end，then we can safely add both to result，
	and mark newInterval as null
			       |________|
	|_ _ _ _ _|
			
3) There is overlap between i and newInterval. We can merge i into newInterval, 
then use the updated newInterval to compare with latter intervals.
	|________|
		|_ _ _ _ _|
			
		|________|
	|_ _ _ _ _|
			
*/

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        
        for(int[] interval : intervals) {
            if(newInterval == null || interval[1] < newInterval[0]) {
                res.add(interval);
            } else if(interval[0] > newInterval[1]) {
                res.add(newInterval);
                res.add(interval);
                newInterval = null;
            } else {
                newInterval[0] = Math.min(interval[0], newInterval[0]);
                newInterval[1] = Math.max(interval[1], newInterval[1]);
            }
        }
        
        if(newInterval != null)
            res.add(newInterval);
        
        return res.toArray(new int[res.size()][]);
    }
}

/*
1. add all the intervals ending before newInterval starts
2. merge all overlapping intervals to one considering newInterval
3. add all the intervals ending before newInterval
*/

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        int i = 0;
        
    // add all the intervals ending before newInterval starts
    while (i < intervals.length && intervals[i][1] < newInterval[0])
        res.add(intervals[i++]);
        
    // merge all overlapping intervals to one considering newInterval
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }        
    res.add(newInterval);
    
    // add all the intervals ending after newInterval
    while (i < intervals.length) 
        res.add(intervals[i++]); 
        
    return res.toArray(new int[res.size()][]);
    }
}