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

Solution:

The idea is to sort the List by Interval.start. (write a comparator)

Then we go through the list and compares the start of current interval with the previous interval's end.

If the start of current interval <= end of previous interval, there is an overlap, we update the end of this overlap.

If the start of current interval > end of previous interval, we know there is no overlap and the current interval can be added to the result.

The sorting takes O(nlogn) and the merge takes O(n). So the overall time complexity is O(n).



Code:

/**
 * 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 == null || intervals.size() == 0) {
            return result;
        }
        
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval x, Interval y) {
                if (x.start != y.start) {
                    return x.start - y.start;
                }
                return x.end - y.end;
            }
        });
        
        result.add(intervals.get(0));
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals.get(i).start <= result.get(result.size() - 1).end) {
                result.get(result.size() - 1).end = 
                    Math.max(result.get(result.size() - 1).end, intervals.get(i).end);
            }
            else {
                result.add(intervals.get(i));
            }
        }

        return result;
    }
}