DAY35贪心算法Ⅳ 重叠区间问题

452. 用最少数量的箭引爆气球 - 力扣（LeetCode）

class Solution {
public:
    static bool cmp(const vector<int>&a, const vector<int>&b){
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size()==0) return 0;
        sort(points.begin(),points.end(),cmp);
        int result=1;
        for(int i=1;i < points.size();i++){
            if(points[i][0] > points[i-1][1]){
                //不挨着，需要多射一箭
                result++;
            }
            else{
                //挨着，更新两球重合的最大end值
                points[i][1]=min(points[i][1],points[i-1][1]);
            }
        }
        return result;
    }
};

435. 无重叠区间 - 力扣（LeetCode）

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(intervals[i][0] >= end){
                //无重叠
                end=intervals[i][1];
            }
            else{
                //重叠
                end=min(end,intervals[i][1]);
                result++;
            }
        }
        return result;
    }
};

763. 划分字母区间 - 力扣（LeetCode）

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;
    int 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;   
    }
};

 重叠类问题要想到按照 左或右 边界进行排序，然后在遍历过程中不断更新 某边界。

划分字母区间要想到使用哈希表。