Add interval to an array of intervals

Merge sorted, non-overlapping list of intervals with another interval.
e.g., Intervals[(1,3), (5,10), (12,30)] + addOne[9,31] = [(1,3), (5,31)]

Update an much neater code. And correct the empty intervals case.

 public class Interval {
      int start;
      int end;
      Interval() { start = 0; end = 0; }
      Interval(int s, int e) { start = s; end = e; }
  }
 
public class InsertInterval {
    public ArrayList insert(ArrayList intervals, Interval newInterval) {
        ArrayList rst = new ArrayList();
        if (intervals == null || newInterval == null)
            return intervals;
            
        Collections.sort(intervals, new IntervalComparator());
        int insert_pos = 0;
        for (Interval intv : intervals)
        {
            if (intv.end < newInterval.start)
            {
                rst.add(intv);
                insert_pos++;
            }
            else if (intv.start > newInterval.end)
                rst.add(intv);
            else
            {
                newInterval.start = Math.min(intv.start, newInterval.start);
                newInterval.end = Math.max(intv.end, newInterval.end);
            }
        }
        rst.add(insert_pos, newInterval);
        return rst;
    }
    private class IntervalComparator implements Comparator
    {
        public int compare(Interval a, Interval b)
        {
             return a.start - b.start;
        }
    }

Start with two conditions:
1. the end point of the added one is smaller than the start point of the first element in the array or the start point of the added one is larger than the end point of the last element in the array. In this case, we simply add the addOne to the top or the bottom of the array, respectively.
2. addOne should be merged into the middle of the array;
In this case, we need to merge the overlapped intervals by finding the start and end point. And add the rest of the intervals to the result list.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;


public class AddInterval {
 public ArrayList add(ArrayList intervals, Interval addOne)
 {
  if (intervals == null || intervals.size() == 0)
   return null;
  Collections.sort(intervals, new IntervalComparator());
  //Two non-overlap boundary cases
  if (addOne.start > intervals.get(intervals.size() - 1).end)
  {
   intervals.add(addOne);
   return intervals;
  }
  if (addOne.end < intervals.get(0).start)
  {
   intervals.add(0, addOne);
   return intervals;
  }
  ArrayList rst = new ArrayList();
  int index = 0;
  //skip all intervals that are "smaller" than addOne
  while (index < intervals.size() && intervals.get(index).end < addOne.start)
  { 
   rst.add(intervals.get(index));
   index++;
   continue;
  }
  Interval tmp = new Interval();
  //find the start point to add
  if (intervals.get(index).start < addOne.start)
   tmp.start = intervals.get(index).start;
  else
   tmp.start = addOne.start;
  //find the end point
  while (index < intervals.size() && intervals.get(index).end < addOne.end)
   index++;
  //if addOne.end is larger than the "end" of the last interval, simply take addOne.end and return 
  if (index == intervals.size() && intervals.get(index - 1).end < addOne.end)
  {
   tmp.end = addOne.end;
   rst.add(tmp);
   return rst;
  }
  if(intervals.get(index).start <= addOne.end)
  {
   tmp.end = intervals.get(index).end;
   index++;
  }
  else
   //current interval is not merged with addOne and has not yet been added to rst
   tmp.end = addOne.end;
  rst.add(tmp);
  
  //add the rest of the intervals
  while (index < intervals.size())
  {
   rst.add(intervals.get(index));
   index++;
  }
  return rst;
 }
 
 private class IntervalComparator implements Comparator
 {
  public int compare(Interval a, Interval b)
  {
   return a.start - b.start;
  }
 }
}