56. 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].

Analysis

link: https://leetcode.com/problems/merge-intervals/discuss/21560/Fast-ana-simple-java-code

The idea is to sort intervals based on start and iterate all intervals to merge them if: curr.end >= iter.start

Solution from Forum

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> res = new LinkedList<Interval>();
        if(intervals.size() < 2) {
            return intervals;
        }
        Collections.sort(intervals, new Comparator<Interval>() {
        @Override
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        });
        Interval curr = intervals.get(0);
        for(Interval iter : intervals) {
            if(curr.end >= iter.start) {
                curr.end = Math.max(curr.end,iter.end);
            }else {
                res.add(curr);
                curr = iter;
            }
        }
        res.add(curr);
        return res;
    }
}