57. Insert Interval Leetcode Java

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

Solution:

It is very similar to the last problem 56. Merge Interval

First of all, we need to find the insertion point, merge the newInterval with all intervals that can be merged from the insertion and add to the result list. If you want to do it in place, then we can just merge them like the last problem(merge interval), and the sublist of the original list.

In place version

 public List<Interval> insert(List<Interval> intervals, Interval newInterval) {  
    if(intervals==null || newInterval==null) return intervals;  
    int inPoint=0;  
    while(inPoint<intervals.size() && newInterval.start>intervals.get(inPoint).end) inPoint++;  
    if(inPoint==intervals.size()){  
      intervals.add(newInterval);  
      return intervals;  
    }  
    intervals.add(inPoint,newInterval);  
    int endPoint=inPoint;  
    for(int i=inPoint+1;i<intervals.size();i++){  
      if(intervals.get(i).start<=intervals.get(endPoint).end){  
        intervals.set(endPoint, new Interval(Math.min(intervals.get(i).start,intervals.get(endPoint).start), Math.max(intervals.get(i).end,intervals.get(endPoint).end)));  
      }  
      else{  
        endPoint++;  
        intervals.set(endPoint,intervals.get(i));  
      }  
    }  
    return intervals.subList(0,endPoint+1);  
   }  

With a new list version

 public List<Interval> insert(List<Interval> intervals, Interval newInterval) {  
    List<Interval> res = new ArrayList<Interval>();  
   if(intervals.size()==0)  
   {  
     res.add(newInterval);  
     return res;  
   }  
   int i=0;  
   while(i<intervals.size() && intervals.get(i).end<newInterval.start)  
   {  
     res.add(intervals.get(i));  
     i++;  
   }  
   if(i<intervals.size())  
     newInterval.start = Math.min(newInterval.start, intervals.get(i).start);  
   res.add(newInterval);  
   while(i<intervals.size() && intervals.get(i).start<=newInterval.end)  
   {  
     newInterval.end = Math.max(newInterval.end, intervals.get(i).end);  
     i++;  
   }  
   while(i<intervals.size())  
   {  
     res.add(intervals.get(i));  
     i++;  
   }  
   return res;  
   }