粗暴方法,先把所有区间按照左边界的大小排序,然后在一个个遍历,如果有重叠部分的就重叠起来,如果没有的就将维护的res-temp变量加入结果数组中,最费劲的是两个区间之间的关系没有搞清楚,花了一些时间,贴代码。
1 bool cmp(vector<int>& a,vector<int>& b) 2 { 3 return a[0]<b[0]; 4 } 5 class Solution { 6 public: 7 vector<vector<int>> merge(vector<vector<int>>& intervals) 8 { 9 sort(intervals.begin(),intervals.end(),cmp); 10 vector<vector<int>> res; 11 vector<int> res_temp = intervals[0]; 12 for(auto inter_temp:intervals) 13 { 14 if(inter_temp[0]<=res_temp[1] && inter_temp[1]>res_temp[1]) 15 { 16 res_temp[1] = inter_temp[1]; 17 } 18 else if(res_temp[1]<inter_temp[0]) 19 { 20 res.push_back(res_temp); 21 res_temp = inter_temp; 22 } 23 } 24 res.push_back(res_temp); 25 return res; 26 } 27 };
没想到我这土方法也能叫双指针,牛。