贪心算法:重叠区间问题。
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.划分字母区间
题目链接:
解题思路:
更新元素最后的出现位置。
代码:
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;
}
};