Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].Example 2:
Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considerred overlapping.顾名思义，合并间隔
那么先排序，维护开头位置s，和递推当前最大能到的位置e
感觉和上一个题差不多
bool cmp(Interval x,Interval y){return (x.start<y.start);} class Solution { public: vector<Interval> merge(vector<Interval>& intervals) { int n=intervals.size(); sort(intervals.begin(),intervals.end(),cmp); vector<Interval> ans; if(n==0) return ans; int maxn=0,s=intervals[0].start,e=intervals[0].end; for(int i=1;i<n;i++){ if(intervals[i].start<=e) e=max(e,intervals[i].end); else{ ans.push_back(Interval(s,e)); s=intervals[i].start; e=intervals[i].end; } } ans.push_back(Interval(s,e)); return ans; } };
