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

一刷
题解：
使用Comparator来对集合进行sort。 Comparator和Comparable是两个很重要的interface，再加上interable，runnable等，要好好掌握。

Time Complexity O(n), space complexity 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 List<Interval> merge(List<Interval> intervals) {
        List<Interval> res = new ArrayList<>();
        if(intervals == null || intervals.size() == 0)
            return res;
        Collections.sort(intervals, new InterComparator());
        
        Interval last = intervals.get(0);
        for(int i=1; i<intervals.size(); i++){
             Interval curr = intervals.get(i);
             if(last.end < curr.start){
                 res.add(last);
                 last = curr;
             }
             else{
                 if(curr.end>last.end){
                     last.end = curr.end;
                 }
             }
        }
        
        res.add(last);
        return res;
    }
    
    public class InterComparator implements Comparator<Interval>{
        public int compare(Interval a, Interval b){
            return a.start - b.start;
        }
    }
}

也可以不用构造新类

  Collections.sort(intervals, new Comparator(){
  public int compare(Interval a, Interval b){
  return a.start - b.start;
}
});

二刷
题解：
先把list按照起始时间ascending排序，然后通过比较end判断是否要merge

/**
 * 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 ArrayList<>();
        if(intervals == null || intervals.size()<=1) return intervals;
        Collections.sort(intervals, new Comparator<Interval>(){
          public int compare(Interval a, Interval b){
              return a.start - b.start;
            }  
            });
        Interval cur = intervals.get(0);
        for(int i=1; i<intervals.size(); i++){
            if(intervals.get(i).start<=cur.end && intervals.get(i).end > cur.end){
                cur.end = intervals.get(i).end;
            }
            else if(intervals.get(i).start>cur.end){
                res.add(cur);
                cur = intervals.get(i);
            }
        }
        res.add(cur);
        return res;
    }
}