贪心算法之区间问题总结

一、跳跃游戏

跳跃游戏类的问题，不关心每一步怎么跳，只需要关心最大覆盖范围

这里注意i是在当前最大可覆盖范围内遍历，如{2,1,0,1}，就是在0~2范围内遍历，千万不能0~numsSize-1范围内遍历！！！

bool canJump(int* nums, int numsSize){//不关心每一步怎么跳，只需要关心最大覆盖范围int cover=0;for(int i=0;i<=cover;i++){cover=fmax(cover,nums[i]);if(cover>=numsSize-1) return true;}return false;
}

二、跳跃游戏II

没见过不好想，建议记下来

关键是当前覆盖范围和下一步覆盖范围都要考虑

计算下一步覆盖范围的目的是用来更新当前覆盖范围，以保证跳跃步数最少

int jump(int* nums, int numsSize){//统计两个覆盖范围:当前这一步的最大覆盖和下一步最大覆盖//如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，//那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点if(numsSize==1) return 0;int curCover=0,nextCover=0;int result=0;for(int i=0;i<=curCover;i++){nextCover=fmax(nextCover,i+nums[i]);if(i==curCover){if(curCover<numsSize-1){result++;curCover=nextCover;if(nextCover>=numsSize-1) break;}else break;}}return result;
}

三、无重叠区间

区间重叠类问题第一步：排序

区间判断重叠方法：若当前区间的右边界大于下一个区间的左边界，则表示有重叠

合并实质上就是更新当前区间的右边界

class Solution {
private:static bool cmp(const vector<int> &a,const vector<int> &b){return a[0]<b[0];}
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {//按照区间左边界从小到大排序//若当前区间的右边界大于下一个区间的左边界，则表示有重叠//可以把移除理解成一种特殊的合并，所有重叠区间合并之后，右边界为最小的那个if(intervals.size()==1) return 0;sort(intervals.begin(),intervals.end(),cmp);int result=0;for(int i=1;i<intervals.size();i++){if(intervals[i-1][1]>intervals[i][0]){intervals[i][1]=fmin(intervals[i-1][1],intervals[i][1]);result++;}}return result;}
};

四、用最少数量的箭引爆气球

实际上这题就是在问：有多少组无重叠区间，和上题都在研究重叠与无重叠区间的问题

注意本题的重叠区间内的所有区间的右边界和上题一样，也要更新为重叠区间里最小的右边界

因为找最大重叠个数的重叠区间看的是“短板”！！！

class Solution {
private:static bool cmp(const vector<int> &a,const vector<int> &b){return a[0]<b[0];}
public:int findMinArrowShots(vector<vector<int>>& points) {if(points.size()==1) return 1;sort(points.begin(),points.end(),cmp);int result=1;for(int i=1;i<points.size();i++){if(points[i-1][1]<pointss[i][0])result++;elsepoints[i][1]=min(points[i-1][1],points[i][1]);}return result;}
};

五、划分字母区间

本题实际上就是在问:求每个闭包的长度

所以关键就是，怎么判断闭包的起始位置

这就和跳跃游戏II有点像了~

class Solution {
public:vector<int> partitionLabels(string s) {//开辟一个数组记录每个字母的最后出现位置int cover[27];for(int i=0;i<s.size();i++)cover[s[i]-'a']=i;//到达最大覆盖距离时（可以理解成这个闭包的最大覆盖范围），//记录该覆盖范围的长度，然后向后移动一个位置int left=0,right=0;vector<int> result;for(int i=0;i<s.size();i++){right=max(right,cover[s[i]-'a']);if(i==right){result.push_back(right-left+1);left=i+1;}}return result;}
};

六、合并区间

所谓合并区间，其实就是重叠区间的右边界取重叠区间内最大右边界

如果下一个区间和当前重叠区间重叠，则更新当前重叠区间的右边界；

若不重叠，说明是新的闭包，上一个重叠区间更新完成，插入result新的重叠区间

class Solution {
private:static bool cmp(const vector<int> &a,const vector<int> &b){return a[0]<b[0];}
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {//所谓合并区间，其实就是重叠区间的右边界取重叠区间内最大右边界//如果下一个区间和当前重叠区间重叠，则更新当前重叠区间的右边界；//若不重叠，说明是新的闭包，上一个重叠区间更新完成，插入result新的重叠区间if(intervals.size()==1) return intervals;sort(intervals.begin(),intervals.end(),cmp);vector<vector<int>> result;result.push_back(intervals[0]);for(int i=1;i<intervals.size();i++){if(intervals[i-1][1]>=intervals[i][0])result.back()[1]=max(intervals[i][1],result.back()[1]);elseresult.push_back(intervals[i]);}return result;}
};