57. Insert Interval (1)

Link

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solution

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int newStart = newInterval[0];
        int newEnd = newInterval[1];
        List<int[]> result = new ArrayList<>();
        for(int i = 0 ; i < intervals.length; i++){
            int curStart = intervals[i][0];
            int curEnd = intervals[i][1];
            
            //no impact the interval while newStart is above the curend
            if(newStart > curEnd){
                result.add(new int[]{curStart, curEnd});    
            }
            //no impact the interval while newEnd is below the curStart
            else if(newEnd < curStart){
                //Add previous newInterval/non-impact interval
                result.add(new int[]{newStart, newEnd});
                
                //Add noimpact part.
                //Tricky here by updating the previous addInterval, we can reuse the logic to update
                //the none-imapct interval, however the last one wouldn't be update, will be handled then.
                newStart = curStart;
                newEnd = curEnd;
            }
            //overlape with the newInterval case
            else{
                //update the newInterval Range by finding the a rational range to meet the existing one
                newStart = Math.min(curStart ,newStart);
                newEnd = Math.max(curEnd ,newEnd);
            }
        }
        
        //The last none-impact interval will be add after exiting the for-loop 
        result.add(new int[]{newStart, newEnd});

        return result.toArray(new int[result.size()][2]);
    }
}