合并区间
按照左边界排序，排序之后局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了，整体最优：合并所有重叠的区间。
其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
class Solution { public: static bool compare(vector<int>&a , vector<int>&b) { return a[0] < b[0]; } vector<vector<int>> merge(vector<vector<int>>& intervals) { if(intervals.size() <= 1) return intervals; vector<vector<int>> result; //按照区间左边界排序 sort(intervals.begin() , intervals.end(),compare); //第一个区间作为临时区间 vector<int> tmp = intervals[0]; for(int i = 1 ; i< intervals.size() ; i++) { //如果当前区间和临时区间有重叠 //取临时区间和当前区间的公共集合作为新的临时区间 if(tmp[1] >= intervals[i][0]) { tmp[0] = min(tmp[0] , intervals[i][0]); tmp[1] = max(tmp[1] , intervals[i][1]); } else//当临时区间和当前区间不重合 { result.push_back(tmp);//临时区间存入 tmp = intervals[i];//当前区间为新的临时区间 } if(i==intervals.size()-1)//当前区间是最后一个区间的时候 { result.push_back(tmp);//存入未存入的临时区间 } } return result; } };
二刷
class Solution { public: static bool cmp(vector<int> &a , vector<int> &b) { return a[0] < b[0]; } vector<vector<int>> merge(vector<vector<int>>& intervals) { vector<vector<int>> result; sort(intervals.begin(),intervals.end(),cmp); for(int i=1 ; i<intervals.size() ;i++) { if(intervals[i][0] <= intervals[i-1][1]) { intervals[i][0] = min(intervals[i][0],intervals[i-1][0]); intervals[i][1] = max(intervals[i][1],intervals[i-1][1]); intervals[i-1][0] = min(intervals[i][0],intervals[i-1][0]); intervals[i-1][1] = max(intervals[i][1],intervals[i-1][1]); } else { result.push_back(intervals[i-1]); } } result.push_back(intervals[intervals.size()-1]); return result; } };
