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]. 看起来感觉不像hard类型的题目，不过要注意的一点是这里给出的数据不一定会像上面这样按照顺序来进行排序，所以处理前首先要按照一定的规则处理一下，写一个functor来进行比较，用struct即可，排序后这个范围就很好确定了，代码如下所示：
1 class Solution { 2 public: 3 vector merge(vector & intervals) { 4 int p = 0, q = 1; 5 std::sort(intervals.begin(), intervals.end(), comp); 6 vector ret; 7 while(q < intervals.size()){ 8 if(intervals[p].end < intervals[q].start){ //这个范围需要记录下来 9 ret.push_back(intervals[p]);10 p = q;11 q++;12 }else{13 if(intervals[p].end < intervals[q].end) //根据条件才更新范围 14 intervals[p].end = intervals[q].end;15 q++;16 }17 }18 if(p < intervals.size())19 ret.push_back(intervals[p]);20 return ret;21 }22 23 24 struct myComparator{25 bool operator()(const Interval & i, const Interval & j){26 return i.start < j.start;27 }28 }comp;29 }; java版本的代码如下所示：
1 public class Solution { 2 public List merge(List intervals) { 3 Collections.sort(intervals, new Comparator (){ 4 public int compare(Interval i1, Interval i2){ 5 return i1.start - i2.start; 6 } 7 }); 8 int sz = intervals.size(); 9 List ret = new ArrayList ();10 if(sz == 0) return ret;11 int prev = 0, next = 1;12 while(next < sz){13 if(intervals.get(prev).end < intervals.get(next).start){14 ret.add(intervals.get(prev));15 prev = next;16 next++;17 }else{18 intervals.get(prev).end = Math.max(intervals.get(prev).end, intervals.get(next).end);19 next++;20 }21 }22 intervals.get(prev).end = Math.max(intervals.get(prev).end, intervals.get(sz-1).end);23 ret.add(intervals.get(prev));24 return ret;25 }26 }