力扣-无重叠区间 & 划分字母区间

435. 无重叠区间

class Solution {
public:
static bool cmp(vector<int> &a, vector<int> &b)
{
    return a[0] < b[0];//按左边界从小到大排
}
//贪心：局部最优推出全局最优
//先按左边界排个序
//当两个重叠时，删掉右边界较大的一个更好
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int pre = 0;//记录上一个区间（就是指当前区间要和上一个区间进行比对，看是否重叠）
        int cnt = 0;//记录需要删除几个
        //先按左边界排序
        sort(intervals.begin(), intervals.end(), cmp);
        for(int i = 1; i < intervals.size(); i++)//从第二个开始遍历
        {
            //和上一个区间对比,如果 当前左边界 大于等于 上一个左边界 并且 小于上一个右边界
            //那么就重叠了
            if(intervals[i][0] >= intervals[pre][0] && intervals[i][0] < intervals[pre][1])
            {
                //此时两者已经重叠，那么删掉右边界较大即可
                cnt++;
                //如果当前的右边界大，难么删掉当前的，pre还是不变，否则删掉上一个，pre更新
                pre = intervals[i][1] > intervals[pre][1] ? pre : i;
            }
            else//如果不重叠
            {
                pre = i;//更新上一个区间
            }
        }
        return cnt;
    }
};

    先排序，然后贪心。需要注意的是，如果不重叠，也要记得更新pre，因为当两个区间不重叠时，下一个区间就要和上一组两个区间种的第二个区间进行比对。

763. 划分字母区间

class Solution {
public:
    vector<int> partitionLabels(string s) {
        //记录每个字母出现的最远下标
        int hash[26] = {0};
        for(int i = 0; i < s.size(); i++)
        {
            hash[s[i] - 'a'] = i;//遇到字符就更新最远下标
        }
        //遍历整个字符串，当遍历位置i和 之前所有字符 最大的出现位置（即最远下标） 相等时
        int maxIndex = 0;
        int left = 0;//记录子串的起始坐标
        int right = 0;//记录子串的最远下标
        vector<int> ans;
        for(int i = 0; i < s.size(); i++)
        {   
            right = max(right, hash[s[i] - 'a']);//更新当前子字符串的最远下标
            //如果当前遍历位置与子串中所有字符中的最远下标相等
            //（也就是其中个别字符的最远下标已经遍历过去了）
            if(i == right)//这个点就是分割点
            {
                ans.emplace_back(right - left + 1);//记录子串个数
                left = i + 1;//更新 新子串的起始位置
            }
        }
        return ans;
    }
};

    这道题被标记为贪心，但确不能用局部最优推出全局最优，很疑惑，我也没做出来。这是代码随想录的思路，记录每个字母的最远下标，然后去遍历字符串，遇到下标相同（即遍历下标和遍历下标所指字母所对应的最远下标），就作为分割点。