day 36贪心（5）

day 36

2024.1.3

1. 435无重叠区间
这道题我的做法与上一道题一致，多加了个记录变化区间范围的标量，本来向删除的，但想了想，没必要，结果返回删除的数量即可，所以将要删除的区间范围更改为不影响判断即可。

class Solution {
public:
    static bool compare(vector<int> a, vector<int> b){
        return a[1]<b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int result = 0;
        sort(intervals.begin(), intervals.end(), compare);
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0] < intervals[i-1][1]){
                result++;
                intervals[i][1] = min(intervals[i][1], intervals[i-1][1]);
            }
        }
        return result;
    }
};

2. 763划分字母区间
这道题开始没思路，看了文字讲解后才明白。方法很巧妙。
分割的地方就是字母最后出现的位置，所以首先利用哈希原理记录每个字母出现的最后位置，然后比大小，直到遇到最大的，也就是最后位置了，则分为一段。以此类推。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hush[27] = {0};
        for(int i=0;i<s.size();i++){
            hush[s[i]-'a'] =i ;
        }
        int left = 0 ;
        int right = 0;
        vector<int> result;
        for(int i=0;i<s.size();i++){
            right = max(right, hush[s[i] - 'a']); 
                if (i == right) {
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};

3. 56合并区间
这道题开始陷入了写代码误区，每次比较跟原始数组比较的，所以结果不正确，最后发现，直接跟result最后一个元素比较就好！

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        if (intervals.size() == 0) return result; // 区间集合为空直接返回
        // 排序的参数使用了lambda表达式
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});

        // 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并
        result.push_back(intervals[0]); 

        for (int i = 1; i < intervals.size(); i++) {
            if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间
                // 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为我们按照左边界排序的
                result.back()[1] = max(result.back()[1], intervals[i][1]); 
            } else {
                result.push_back(intervals[i]); // 区间不重叠 
            }
        }
        return result;
    }
};