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

?

?

題目沒有說所有間隔的start是依次增加的。所以，為了方便討論，我們要將所有間隔按照start升序排列。因為間隔增加，就只需討論end和下一個間隔。
結果集中是沒有交叉出現的，排序后，遍歷下一個時，只會跟結果集最后一個產生交叉，而不會跟在前的結果產生交叉（因為結果集中，最后一個間隔的start>前一個的end）
排列結束后，我們只需要討論后一個跟前一個結果，如果后一個間隔的start大于前一個結果集中的間隔的end，那么沒有交叉，直接添加 結果集。
否則該間隔就和結果集中最后一個間隔有交叉，這時要討論該間隔的end和結果集中最后一個間隔的end大小，前者大，就要刪除結果集最后一個，然后將前者加入結果集；如果后者大，說明只是end和start交叉了，這樣刪除結果集最后一個，添加新的間隔。見代碼。

?

/*** 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; }* }*/
class Solution {public List<Interval> merge(List<Interval> intervals) {List<Interval> res=new ArrayList<Interval>();if(intervals==null||intervals.size()<=1) return intervals;Collections.sort(intervals,new Comparator<Interval>(){public int compare(Interval o1,Interval o2){return o1.start-o2.start;}});res.add(intervals.get(0));for(int i=1;i<intervals.size();i++){Interval in1=res.get(res.size()-1);  //結果集中最后一個間隔，用于比較Interval in2=intervals.get(i);  //當前間隔，只會與結果集中最后一個間隔產生交集。if(in1.end<in2.start) res.add(in2); //沒有交叉。直接加入else { //有交叉if(in1.end>=in2.end) continue;//前一個包含后一個，跳過else{  //只是start和end交叉res.remove(res.size()-1);res.add(new Interval(in1.start,in2.end));}}}return res;}
}

?