Merge Intervals

Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].

• Time: O(n)
• Space: O(1)

public List<Interval> merge(List<Interval> intervals) {
    if (intervals.size() <= 1) {
        return intervals;
    }
    Collections.sort(intervals, (a, b) -> a.start - b.start);
    List<Interval> ret = new ArrayList<>();
    Interval pre = intervals.get(0);
    for (int i = 1; i < intervals.size(); i++) {
        Interval cur = intervals.get(i);
        if (pre.end < cur.start) {
            ret.add(pre);
            pre = cur;
        } else {
            pre.end = Math.max(cur.end, pre.end);
        }
    }
    ret.add(pre);
    return ret;
}