Insert Interval

For this problem, the first thing I believe is to find out where I should put the newInterval.start and newInterval.end, and based on the value of newInterval, then determine how to merge this newInterval, or just to insert it in the right place. What is tricky is that some special cases might not be considered at first, and this problem really needs us to be careful.


/**
 * 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) {
        if (intervals == null || newInterval == null) return null;
        if (newInterval.start > newInterval.end) return null;
        int insertStartIdx = findIdxBehind(intervals, newInterval.start,0);
        int insertEndIdx = findIdxBehind(intervals, newInterval.end,insertStartIdx);
       
        if(intervals.isEmpty()) {intervals.add(newInterval); return intervals;}// Inspired by the case of [], [1 3]
       
       if(insertStartIdx == intervals.size() - 1){
           intervals.add(newInterval);
           return intervals;
        }
            int mergeStart;
            int mergeEnd;

                if(intervals.get(insertStartIdx+1).start < newInterval.start){
                    mergeStart = intervals.get(insertStartIdx+1).start;
                }
                else{
                    mergeStart = newInterval.start;
                }
           
            if(insertEndIdx == intervals.size()-1){
                mergeEnd = newInterval.end;
                Interval insertInterval = new Interval(mergeStart,mergeEnd);
                removeRange(intervals, insertStartIdx+1,insertEndIdx+1);
                intervals.add(insertStartIdx + 1, insertInterval);
            }
            else{
            boolean flag = false;  
               if(intervals.get(insertEndIdx+1).start <= newInterval.end){
                   if(intervals.get(insertEndIdx+1).end > newInterval.end)
                    mergeEnd = intervals.get(insertEndIdx+1).end;
                    else mergeEnd = newInterval.end;
                }
                else{
                    flag =true;
                    mergeEnd = newInterval.end;
                }
                Interval insertInterval = new Interval(mergeStart,mergeEnd);
                if(flag){
                        removeRange(intervals,insertStartIdx + 1,insertEndIdx+1);
                }
                else
                    removeRange(intervals, insertStartIdx + 1,insertEndIdx + 2);
                if(!intervals.contains(insertInterval))intervals.add(insertStartIdx + 1, insertInterval);
            }
        // }
        return intervals;
    }
   
    public int findIdxBehind(ArrayList<Interval> intervals, int insertVal, int startIdx){// find the index at which i the intervals.get(i).end < insertVal, while intervals.get(i+1).end >= insertVal
        if (startIdx < 0) startIdx = 0;
        while(startIdx < intervals.size()){
            if (intervals.get(startIdx).start > insertVal) return --startIdx;
            else if(intervals.get(startIdx).end >= insertVal) return --startIdx;// previously, end >= insertVal
                 else startIdx ++;
        }
        return --startIdx;
    }
    public void removeRange(ArrayList<Interval> intervals, int fromIdx, int toIdx){// since ArrayList.removeRange is protected, write it myself
        while(fromIdx < toIdx && fromIdx < intervals.size()){
            intervals.remove(fromIdx);
            toIdx --;// be careful of this, previously, I wrote from ++
        }
    }
}