Merge Intervals

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

Naive Way:  排序，然后用greedy的思想不断兼并下一个。

算法复杂度因为排序的原因是O(nlogn)。space是O(n)。

/**
 * 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.size()==0){return intervals;}
        Interval[] arr = new Interval[intervals.size()];
        Comparator<Interval> c = new Comparator<Interval>(){
            public int compare(Interval x, Interval y){
                if(x.start < y.start){
                    return -1;
                }else if(x.start > y.start){
                    return 1;
                }else{
                    if(x.end < y.end){
                        return -1;
                    }else if(x.end > y.end){
                        return 1;
                    }
                }
                return 0;
            }
        };
        for(int i = 0;i < arr.length;i++)
            arr[i] = intervals.get(i);
        Arrays.sort(arr, c);
        intervals.clear();
        int s = arr[0].start;
        int e = arr[0].end;
        int i = 0;
        while(++i < arr.length){
            if(arr[i].start <= e){
                e = Math.max(arr[i].end,e);
            }else{
                Interval interval = new Interval(s,e);
                intervals.add(interval);
                s = arr[i].start;
                e = arr[i].end;
            }
        }
        Interval interval = new Interval(s,e);
        intervals.add(interval);
       
        return intervals;
    }
}

Improved Way: 对于排序的处理应该用更简单的collection.sort,并且排序时可以不管end，因为start一致的时候end无论大小都会被融合进同一个interval里。

 Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        });