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;
}
}