代码随想录算法训练营第三十六天|435. 无重叠区间、763.划分字母区间、56. 合并区间

题目：435. 无重叠区间

文章链接：代码随想录

视频链接：LeetCode:435.无重叠区间

题目链接：力扣题目链接

图释：

class Solution {
public:
    static bool cmp(const vector<int>&a, const vector<int>&b){
        return a[0] < b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // if(intervals.size() == 0 ||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]){
                result++;
                intervals[i][1] = min(intervals[i-1][1], intervals[i][1]);
            }
        }
        return result;
    }
};

题目：763.划分字母区间

文章链接：代码随想录

视频链接：LeetCode:763.划分字母区间

题目链接：力扣题目链接

图释：

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hash[27]={0};
        for(int i=0; i<s.size(); i++){
            // s[i]-'a' ask||码，对应下标
            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;
    }
};

题目：56. 合并区间

文章链接：代码随想录

视频链接：LeetCode:56.合并区间

题目链接：力扣题目链接

图释：

class Solution {
public:
    static bool cmp(const vector<int>&a, const vector<int>&b){
         return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size()<=1) return intervals;
        vector<vector<int>> result;
        vector<int> path;
        sort(intervals.begin(), intervals.end(), cmp);
        path.push_back(intervals[0][0]);
        for(int i=1; i<intervals.size(); i++){
            if(intervals[i-1][1] >= intervals[i][0]){
                // 更新右边边界
                intervals[i][1] = max(intervals[i][1], intervals[i-1][1]);
            }else{//没有重叠
                 path.push_back(intervals[i-1][1]);
                 result.push_back(path);
                 path.clear();
                 path.push_back(intervals[i][0]);
            }
        }
        path.push_back(intervals[intervals.size()-1][1]);
        result.push_back(path);
        return result;
    }
};