Leetcode: Insert Interval

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:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Understand the Problem:

This problem is very similar to merge interval. The question asks for given a set of non-overlapping intervals, insert a new interval into the intervals, and merge them, if necessary. 

So the question can be divided by two steps: insert and merge. 

Also note that the intervals has already been sorted initially.

Solution:
Since the problem can be divided by two steps, insert and merge, we can do it step by step. Insertion is very simple, we just need to scan the input intervals and compare the start value until we found one is larger than the insert interval. Then we insert the token into the ArrayList. The merge process will be exactly the same as the Merge Interval problem. 

Code (Java):

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        ArrayList<Interval> result = new ArrayList<Interval>();
        
        // check if the list is empty or null
        if (intervals == null || newInterval == null) return result;
        
        if (intervals.isEmpty()) {
            result.add(newInterval);
            return result;
        }
        
        // find the insertion point and insert the new newInterval
        for (int i = 0; i < intervals.size(); i++) {
            if (intervals.get(i).start > newInterval.start) {
                intervals.add(i, newInterval);
                break;
            }
        }
        // insert at end of the list
        intervals.add(newInterval);
        
        // merge the overlapped intervals
        Interval prev = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (isOverlapped(prev, curr)) {
                Interval temp = new Interval();
                temp.start = prev.start;
                temp.end = Math.max(prev.end, curr.end);
                prev = temp;
            } else {
                result.add(prev);
                prev = curr;
            }
        }
        result.add(prev);
        
        return result;
    }
    
    private boolean isOverlapped(Interval prev, Interval curr) {
        return curr.start <= prev.end;
    }
}

Discussion:
Note the method add(int index, E element) inserts the elements into the current index.  Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices). That's why we could use add() instance method and no worry it is replace the value in the insertion position. In addition, when we insert a value, take care if the value is greater than the largest one in the list. In this case, we have to insert the value at the end of the end, as is shown in Line 30 of the code. This is a tricky bug we are easily to forget. 

Note that this solution has two downsides. First of all, intervals.add() will modify the input parameters, which is sometimes not allowed. Second, insert an number at middle will cause the shift of all its right elements. 



A Better Solution:
Does there exist a better solution without needing to modify the input parameters? The answer is yes. Re-think the question. We are not actually required to insert an interval into the original. We are only asked to return the final merged list. 

Following this idea, we could decide when we insert an internal, what needs to be inserted into the result list. There are three cases:
1. For the current interval is less than the newInterval, i.e, the end of current interval is less than the start of newInterval. Then there must have no overlapping. In this case, we only need to insert the current interval into the result list. 
2. For the current interval is greater than the newInterval. That is, the start of the current interval is greater than the end of newInterval. In this case, we insert the newInterval into the result list, and update the newInterval as current interval. 
3. For other cases where we have overlapped regions. We merge the two intervals and update the newInterval. 

Code (Java):

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        ArrayList<Interval> result = new ArrayList<Interval>();
        
        if (newInterval == null) return intervals;
        
        if (intervals == null || intervals.size() == 0) {
            result.add(newInterval);
            return result;
        }
        
        Interval prev = newInterval;
        
        for (Interval curr : intervals) {
            // if curr interval is greater than prev
            if (curr.start > prev.end) {
                result.add(prev);
                prev = curr;
            } else if (curr.end < prev.start) {
                result.add(curr);
            } else {
                prev.start = Math.min(prev.start, curr.start);
                prev.end = Math.max(prev.end, curr.end);
            }
        }
        result.add(prev);
        return result;
    }
}

Summary:
The problem is not hard at the first glance, but very tricky to come out the second solution. If you follow the hint of the question you will insert then merge. Then you have to modify the input array to insert the new inserted point.  A smarter way is to compare each interval from the input array with the insertion interval, and determine if they overlapped. We only need to insert the interval when they are not overlapped. This is quite close to the merge interval question.