代码随想录算法训练营第三十六天|435. 无重叠区间、763.划

435. 无重叠区间

按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了

// 按照区间右边界排序staticboolcmp(constvector<int>&a,constvector<int>&b){returna[1]<b[1];}interaseOverlapIntervals(vector<vector<int>>&intervals){if(intervals.size()==0)return0;sort(intervals.begin(),intervals.end(),cmp);intcount=1;// 记录非交叉区间的个数intend=intervals[0][1];// 记录区间分割点for(inti=1;i<intervals.size();i++){if(end<=intervals[i][0]){end=intervals[i][1];count++;}}returnintervals.size()-count;} 

763.划分字母区间 

可以分为如下两步：

统计每一个字符最后出现的位置

从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

vector<int>partitionLabels(string S){inthash[27]={0};// i为字符，hash[i]为字符出现的最后位置for(inti=0;i<S.size();i++){// 统计每一个字符最后出现的位置hash[S[i]-'a']=i;}vector<int>result;intleft=0;intright=0;for(inti=0;i<S.size();i++){right=max(right,hash[S[i]-'a']);// 找到字符出现的最远边界if(i==right){result.push_back(right-left+1);left=i+1;}}returnresult;}

56. 合并区间

按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1] 即intervals[i]的左边界 <= intervals[i - 1]的右边界，则一定有重叠

vector<vector<int>>merge(vector<vector<int>>&intervals){vector<vector<int>>result;if(intervals.size()==0)returnresult;// 区间集合为空直接返回// 排序的参数使用了lambda表达式sort(intervals.begin(),intervals.end(),[](constvector<int>&a,constvector<int>&b){returna[0]<b[0];});// 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并result.push_back(intervals[0]);for(inti=1;i<intervals.size();i++){if(result.back()[1]>=intervals[i][0]){// 发现重叠区间// 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为我们按照左边界排序的result.back()[1]=max(result.back()[1],intervals[i][1]);}else{result.push_back(intervals[i]);// 区间不重叠 }}returnresult;}