/**
 * 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; }
 * }
 */
 /*
 * Thought:
 *  1. sort the list by the start
 *  2. compare two Interval, the firstInterval.end > secondInterval.start  merge these two Intervals
 *  3. the mergedInterval{ start = firstInterval.start, end = Math.max(firstInterval.end, secondInterval.end)}
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> resultLst = new ArrayList<Interval>();
        Interval lastIntval;
        if(intervals.size() == 0)
            return resultLst;
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
              return a.start - b.start;
            }
        });
        lastIntval = intervals.get(0);
        for(int i = 0; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if(lastIntval.end < curr.start) {
                resultLst.add(lastIntval);
                lastIntval = curr;
            } else {
                //merge the two intervals
                lastIntval.end = Math.max(lastIntval.end, curr.end);
            }
        }
        resultLst.add(lastIntval);
        return resultLst;
    }
}