Loop Solution - Insert Interval - centrate loop*

The idea is to loop from begin and end, set the begin index and end index,  which would be the new interval in the result. Instead of removing from the passed list, a result list is defined and add values when not in the new interval overlap, or new interval with new being index and end index.

Because of the possible merge, it would be a good idea to separate the loop that loops the start from the begin, and the end from the tail, then locate the new Start and new End. New values are used as flags to verify if new interval found.


/**
 * 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(newInterval == null){
            return intervals;
        }
        ArrayList<Interval> res = new ArrayList<Interval>();//create a new one instead of removing from the old one.
        if(intervals == null || intervals.size() == 0){
            res.add(newInterval);
            return res;
        }
        int newBeginInterval = -1;
        int i  = 0;
        int newEndInterval = -1;
        int j = intervals.size() - 1;
        while(i <= j){
            if(newInterval.start >= intervals.get(i).start && newInterval.start <= intervals.get(i).end){
                newBeginInterval = intervals.get(i).start;
            }else if(i == 0 && newInterval.start < intervals.get(i).start){
                newBeginInterval = newInterval.start;
            }else if(i > 0 && newInterval.start < intervals.get(i).start && newInterval.start > intervals.get(i - 1).end){
                newBeginInterval = newInterval.start;
            }else{
                res.add(i, intervals.get(i)); // add i to guarantee the order in the res list.!!!
                i++;
            }
           
            if(newInterval.end >= intervals.get(j).start && newInterval.end <= intervals.get(j).end){
                newEndInterval = intervals.get(j).end;
            }else if(j == intervals.size() - 1 && newInterval.end > intervals.get(j).end){
                newEndInterval = newInterval.end;
            }else if(j < intervals.size() - 1 && newInterval.end < intervals.get(j + 1).start && newInterval.end > intervals.get(j).end){
                newEndInterval = newInterval.end;
            }else{
                //if(i != j || res.isEmpty()){  //potential bug for duplicates if i == j
                res.add(i,intervals.get(j)); // i to ensure the order
                //}
                j--;
            }
           
            if(newBeginInterval != -1 && newEndInterval != -1){
                res.add(i, new Interval(newBeginInterval, newEndInterval));
                break;
            }
        }
        if(newBeginInterval == -1 || newEndInterval == -1){  // or because always one side is set!!!
            if(newInterval.start > intervals.get(intervals.size() - 1).end){
                //res.addAll(intervals);
                res.add(newInterval);
            }else if(newInterval.end < intervals.get(0).start){
                res.add(0, newInterval);
                //res.addAll(intervals);
            }else{   //!!! 1-5, 12-15 / 6-6.... i and j will be ++ and -- at the same time, 6-6 will be missed....in this case...!!!
                res.add(i, newInterval);
            }
        }
        return res;//return
    }
}