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:

假设这些interval是有序的（也就是说先按起始点排序，然后如果起始点相同就按结束点排序），那么要把它们合并就只需要按顺序读过来，如果当前一个和结果集中最后一个有重叠，那么就把结果集中最后一个元素设为当前元素的结束点（不用改变起始点因为起始点有序，因为结果集中最后一个元素起始点已经比当前元素小了）。那么剩下的问题就是如何给interval排序，在java实现中就是要给interval自定义一个Comparator，规则是按起始点排序，然后如果起始点相同就按结束点排序。整个算法是先排序，然后再做一次线性遍历，时间复杂度是O(nlogn+n)=O(nlogn)，空间复杂度是O(1)，因为不需要额外空间，只有结果集的空间。

/**
 * 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 ArrayList merge(ArrayList intervals) {
        if(intervals == null || intervals.size() == 0) 
            return intervals;
        
        ArrayList res = new ArrayList();
        
        //defining a Comparator first to sort the arraylist of Intevals
        Comparator comp = new Comparator() {
            @Override
            public int compare(Interval i1, Interval i2) {
                if(i1.start == i2.start)
                    return i1.end - i2.end;
                return i1.start - i2.start; 
            }
        };

        //sort intervals by using self-defined Comparator
        Collections.sort(intervals, comp); 
        
        Interval pre = intervals.get(0);
        for(int i = 1; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            if(pre.end >= cur.start) {  //merge some intervals
                Interval merge = new Interval(pre.start, Math.max(pre.end, cur.end));
                pre = merge;
            }else {
                res.add(pre);
                pre = cur;
            }
        }
        res.add(pre);
        return res;
    }
}