本文主要是介绍算法训练营第36天|LeetCode 435.无重叠区间 763.划分字母区间 56.合并区间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
贪心算法：重叠区间问题。
LeetCode 435.无重叠区间
题目链接：
LeetCode 435.无重叠区间
解题思路：
更新重叠最小右边界。
代码：
class Solution {
public:static bool cmp(vector<int>a,vector<int>b){return a[0]<b[0];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if(intervals.size()==0) return 0;sort(intervals.begin(),intervals.end(),cmp);int result=0;int end = intervals[0][1];for(int i=1;i<intervals.size();i++){if(end<=intervals[i][0]){end = intervals[i][1];}else{result++;end = min(intervals[i][1],end);}}return result;}
};LeetCode 763.划分字母区间
题目链接：
LeetCode 763.划分字母区间
解题思路：
更新元素最后的出现位置。
代码：
class Solution {
public:vector<int> partitionLabels(string s) {int hash[27] = {0};for(int i=0;i<s.size();i++){hash[s[i]-'a']=i;}vector<int>result;int left=0,right=0;for(int i=0;i<s.size();i++){right = max(right,hash[s[i]-'a']);if(i==right){result.push_back(right-left+1);left = i+1;}}return result;}
};LeetCode 56.合并区间
题目链接：
LeetCode 56.合并区间
解题思路：
更新不重叠的区间大小。
代码：
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);if(intervals.size()==0) return result;if(intervals.size()==1) return intervals;int left = intervals[0][0],right = intervals[0][1];for(int i =1;i<intervals.size();i++){if(right<intervals[i][0]){result.push_back({left,right});left = intervals[i][0];right = intervals[i][1];if(i==intervals.size()-1){result.push_back({left,right});}}else{left = min(left,intervals[i][0]);right = max(right,intervals[i][1]);if(i==intervals.size()-1){result.push_back({left,right});}}}return result;}
};这篇关于算法训练营第36天|LeetCode 435.无重叠区间 763.划分字母区间 56.合并区间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
