Thinking process

Sort the intervals by starting time.

From the second one, if it's overlapped with the first, update the ending time of first.

If the third is not overlapped, then add the previous interval to the result; if it's overlapped, update the ending time again

Mistakes

1. what if [1,4], [4,5]?
2. current interval should compare with the interval at pos

/**
 * 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> merge(List<Interval> intervals) {
        List<Interval> result = new ArrayList<>();
        if (intervals.size() <= 1) return intervals;

        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval i1, Interval i2) {
                return i1.start - i2.start;
            }
        });

        int pos = 0;

        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals.get(i).start <= intervals.get(pos).end) {
                if (intervals.get(i).end > intervals.get(pos).end) {
                    intervals.get(pos).end = intervals.get(i).end;
                }    
            } else {
                result.add(intervals.get(pos));
                pos = i;
            }
        }

        result.add(intervals.get(pos));

        return result;
    }
}