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

思路：用Collections.sort。是一种比Arrays.sort更广泛的东西

/**
 * 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() <= 1)
        return intervals;

        Comparator<Interval> comp = new Comparator<Interval>(){
            public int compare(Interval a, Interval b){
                return a.start - b.start;
            }
        };

        Collections.sort(intervals,comp);

        List<Interval> res = new ArrayList<Interval>();
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (Interval inter : intervals){
            if (inter.start<=end){
                end = Math.max(end,inter.end);
            }else{
                res.add(new Interval(start,end));
                start = inter.start;
                end = inter.end;
            }
        }
        res.add(new Interval(start, end));
        return res;
    }
}

思路2: 就用Arrays.sort(); 先分别sort所有intervals的start和end，再比较end(i)和start(i+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 List<Interval> merge(List<Interval> intervals){
        List<Interval> res = new LinkedList<Interval>();
        if(intervals == null)
            return res;
        int[] start = new int[intervals.size()];
        int[] end = new int[intervals.size()];
        for(int i = 0; i < intervals.size(); i++){
            start[i] = intervals.get(i).start;
            end[i] = intervals.get(i).end;
        }

        Arrays.sort(start);
        Arrays.sort(end);

        int i = 0;
        while(i<intervals.size()){
            int newStart = start[i];
            while(i<intervals.size()-1 && start[i+1] <= end[i]){
                i++;
            }
            int newEnd = end[i];
            Interval newInterval = new Interval(newStart,newEnd);
            res.add(newInterval);
            i++;
        }
        return res;
    }
}