week6 57. Insert Interval

/**
 * 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> result = new ArrayList<Interval>();
    if (intervals.isEmpty()) {
      result.add(newInterval);
      return result;
    }

    int i = 0;
    while (i < intervals.size() && newInterval.start > intervals.get(i).end) {
      result.add(intervals.get(i));
      i++;
    }

    result.add(newInterval);

    while (i < intervals.size() && overlap(newInterval, intervals.get(i))) {
      Interval interval = intervals.get(i);
      newInterval.start = Math.min(newInterval.start, interval.start);
      newInterval.end = Math.max(newInterval.end, interval.end);
      i++;
    }

    while (i < intervals.size()) {
      result.add(intervals.get(i));
      i++;
    }
    return result;
  }

  private static boolean overlap(Interval i1, Interval i2) {
    return i1.start >= i2.start && i1.start <= i2.end || i2.start >= i1.start
        && i2.start <= i1.end;
  }
}