Merge Intervals

Problem

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]

Solution

/**
 * 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) {
        if (intervals == null || intervals.size() <= 1) return intervals;
        List<Interval> res = new ArrayList<>();
        Collections.sort(intervals, (a, b) -> a.start - b.start);
        res.add(intervals.get(0));
        for (int i = 1; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            Interval last = res.get(res.size() - 1);
            if (cur.start <= last.end) last.end = Math.max(last.end, cur.end);
            else res.add(cur);
        }
        return res;
    }
}

Analysis

Sort the given intervals and simply check each interval and add to the res
While checking, we just need to see if the current interval overlaps the last interval from res
If so, we need to set last.end with larger end since ArrayList only stores the reference
cur = [1, 5], last = [2, 3] => cur = [1, 5]
If not, just add the cur to our res