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

这个题目很容易出现的一个bug就是: 只merge最开始可以merge的那些, 而后面的没有merge.

先看一段代码:

 public class Solution {  
   public List<Interval> merge(List<Interval> intervals) {  
     if (intervals == null || intervals.size() < 2)  
       return intervals;  
     List<Interval> ans = new ArrayList<Interval>();  
     Collections.sort(intervals);  
     int pre = 0, curr = 1;  
     while (curr < intervals.size() && intervals.get(pre).end < intervals.get(curr).start) {  
       ans.add(intervals.get(pre));  
       pre = curr;  
       curr++;  
     }  
     int newStart = intervals.get(pre).start, newEnd = intervals.get(pre).end;  
     while (curr < intervals.size() && newEnd >= intervals.get(curr).start) {  
       newStart = Math.min(newStart, intervals.get(curr).start);  
       newEnd = Math.max(newEnd, intervals.get(curr).end);  
       curr++;  
     }      
     Interval newOne = new Interval(newStart, newEnd);  
     ans.add(newOne);  
     while (curr < intervals.size()) {  
       ans.add(intervals.get(curr));  
       curr++;  
     }  
     return ans;  
   }  
 }  

Input:	[[2,3],[2,2],[3,3],[1,3],[5,7],[2,2],[4,6]]
Output:	[[1,3],[4,6],[5,7]]
Expected:	[[1,3],[4,7]]

这个时候的问题就是: 第一组可以merge的interals全部被merge好了. 但是之后的intervals都left as their original. 问题就出在了中间斜体加粗的代码.

所以应该时刻让pre跟着curr, 从始至终都要跟着, 一旦发现了可以merge的就采取措施, 不断更新pre.
下面看正确的代码: 

 public class Solution {  
   public List<Interval> merge(List<Interval> intervals) {  
     if (intervals == null || intervals.size() < 2)  
       return intervals;  
     List<Interval> ans = new ArrayList<Interval>();  
     Collections.sort(intervals);  
     Interval pre = intervals.get(0);  
     for (int i=1; i<intervals.size(); i++) {  
       Interval curr = intervals.get(i);  
       if (pre.end < curr.start) {  
         ans.add(pre);  
         pre = curr;  
       }else {  
         pre.end = Math.max(pre.end, curr.end);  
         pre.start = Math.min(pre.start, curr.start);  
       }  
     }  
     ans.add(pre);  
     return ans;  
   }  
 }  

Note: 千万注意, get(0)要在sort之后, 因为后面的操作都是建立在已经sort好的一个Interval list上的!!!!!!!!!!!