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].


Naive Way: This question contains no fancy algorithm as far as I know. Just find where the new interval should be merged into. I try to implement it naively in one pass. But there are so many edge cases I never thought about. I list some of them.

• Empty set of intervals [].
• New interval doesn't have overlap with any of the intervals in the set.
• New interval is before first interval of the set.
• New interval is after last interval of the set.

After including all these edge cases. My code is a little tedious. Use a new List to hold result, which requires O(n) space.

 /**  
  * 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 List<Interval> insert(List<Interval> intervals, Interval newInterval) {  
     List<Interval> rslt = new ArrayList<Interval>();  
     // edge case  
     if(intervals.size()==0) rslt.add(newInterval);  
     // merge intervals  
     int begin = -1, end = -1;  
     for(int i = 0;i < intervals.size();i++){  
       // if no overlapping with newInterval at all  
       if(intervals.get(i).start > newInterval.end && i==0)  
         rslt.add(newInterval);  
       // if current interval overlap with newInterval, merge them  
       if(overlap(intervals.get(i), newInterval)){  
         if(begin==-1) begin = Math.min(intervals.get(i).start, newInterval.start);  
         end = Math.max(intervals.get(i).end, newInterval.end);  
         // when last interval overlaps  
         if(i==intervals.size()-1){  
           Interval mergedInterval = new Interval(begin, end);  
           rslt.add(mergedInterval);  
         }  
       }else{  
         if(begin!=-1){  
           // if overlap ends, add newly merged interval  
           Interval mergedInterval = new Interval(begin, end);  
           rslt.add(mergedInterval);  
           begin = -1;  
         }  
         rslt.add(intervals.get(i));  
       }  
       // if no overlapping with newInterval at all  
       if(intervals.get(i).end < newInterval.start && (i!=intervals.size()-1 && intervals.get(i+1).start > newInterval.end || i==intervals.size()-1))  
         rslt.add(newInterval);  
     }  
     return rslt;  
   }  
   private boolean overlap(Interval a, Interval b){  
     if(a.start <= b.start)  
       return a.end >= b.start;  
     else  
       return b.end >= a.start;  
   }  
 }  

Improved Way: There are much better and concise Solutions in Discuss Board. I steal one from inplace-and-concise-lines-java-solution-for-your-reference.
Its idea is to find the correct position for new interval, merge if necessary.

 public class Solution {  
   public List<Interval> insert(List<Interval> intervals, Interval newInterval) {  
     Iterator<Interval> iter = intervals.iterator();  
     int index = 0;  
     while(iter.hasNext()){  
       Interval cur = iter.next();  
       if(cur.end < newInterval.start){ index++; continue;}  
       if(cur.start > newInterval.end) break;  
       newInterval.start = Math.min(newInterval.start, cur.start);  
       newInterval.end = Math.max(newInterval.end, cur.end);  
       iter.remove();  
     }  
     intervals.add(index, newInterval);  
     return intervals;  
   }  
 }