56. Merge Intervals

/**
 * 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; }
 * }
 */

class Solution {
  
  public List<Interval> merge(List<Interval> intervals) {
    if (intervals == null || intervals.size() < 2) return intervals;

    Collections.sort(intervals, new Comparator<Interval>() {
      @Override
      public int compare(Interval a, Interval b) {
        return a.start - b.start;
      }
    });

    List<Interval> sol = new ArrayList<Interval>();

    int start = intervals.get(0).start;
    int end = intervals.get(0).end;

    for (int i = 1; i < intervals.size(); i++) {
      Interval interval = intervals.get(i);

      if (interval.start <= end) {
        end = Math.max(interval.end, end);
      } else {
        sol.add(new Interval(start, end));

        start = interval.start;
        end = interval.end;
      }
    }

    sol.add(new Interval(start, end));

    return sol;
  }
}