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

435.无重叠区间

题目链接：435.无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

文章讲解/视频讲解：https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html

思路

贪心的思路如下图所示，首先按照右边界对区间进行排序。然后从左向右记录非交叉区间。

如上图，区间1、2、3重合，在移除时，需要移除区间2和区间3，保留右边界最小的区间1。因为非交叉
区间是按照右边界来判断的，只要一个区间的左边界小于一个非交叉区间的最小右边界，那么这个区间
就属于这个非交叉区间。上一句话的前提是这个区间和非交叉区间中的其他区间连续，例如，如果区间5
的左边界小于区间1的右边界，依然不能划入第一个非重合区间中。

反之，如果一个区间不属于这个非交叉区间，那么这个区间要么左边界大于等于这个非交叉区间的最小
右边界，要么这个区间在下一个非交叉区间中要被移除。对于第二种情况，设想一下区间5的左边界小于
区间1的右边界，区间5属于第二个非交叉区间，这时，因为区间5的右边界大于区间4的右边界，需要保
留的是区间4，区间5会被剔除。因此，我们可以放心地保留非交叉区间种右边界最小的区间（即非交叉
区间中的第一个区间），这个区间与后续的剔除后的区间一定不重叠。

如果是按照左边界对区间进行排序，那就需要从右往左记录非交叉区间了。

排序的时候，用数据的引用，而不是直接传形参。这样会快很多。

C++实现

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size() == 0) return 0;
        auto cmp = [](const vector<int>& a,const vector<int>& b){return a[1] < b[1];};
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 1;
        int minRight = intervals[0][1];
        for(int i = 1;i<intervals.size();i++){
            if(intervals[i][0] >= minRight){
                minRight = intervals[i][1];
                count++;
            }
        }
        return intervals.size() - count;
    }
};

763.划分字母区间

题目链接：763.划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

文章讲解/视频讲解：https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html

思路

第一遍遍历，用一个哈希表hash来记录下每个字母出现的次数。

第二遍遍历，每遍历一位字母，判断一下当前区间中的字母是否还剩余，比如对于字母a，用hash[‘a’]减
去已经遍历到的字母a的个数，如果等于0，说明所有字母a都已经遍历完了。如果对于当前区间中的所有
字母，都没有剩余了，那就可以进入下一个区间。

需要对tmpHash做一下clear操作。

也可以统计一下每一个字符最后出现的位置，然后在遍历的过程中，如果当前遍历到了当前区间内字符
中最后出现的位置，则找到了一个划分位置。

C++实现

// 原本写法
class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> hashSet(26, 0);
        for(int i = 0;i<s.size();i++){
            hashSet[s[i] - 'a']++;
        }
        vector<int> results;
        vector<int> tmpHash(26, 0);
        for(int i = 0;i<s.size();i++){
            tmpHash[s[i] - 'a'] += 1;

            bool finished = true;
            int sum = 0;
            for(int j = 0;j<tmpHash.size();j++){
                if(tmpHash[j] != 0 && tmpHash[j] != hashSet[j]){
                    finished = false;
                }
                sum += tmpHash[j];
            }
            if(finished){
                tmpHash.clear();
                tmpHash.resize(26, 0);
                results.push_back(sum);
            }
        }

        return results;
    }
};

// 统计字符最后出现的位置
class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> hashSet(26, 0);
        for(int i = 0;i<s.size();i++){
            hashSet[s[i] - 'a'] = i;
        }
        vector<int> results;

        int maxEnd = 0;
        int left = 0;
        for(int i = 0;i<s.size();i++){
            maxEnd = max(maxEnd, hashSet[s[i] - 'a']);
            if(maxEnd == i){
                results.push_back(i - left + 1);
                left = i + 1;
            }
        }

        return results;
    }
};

56. 合并区间

题目链接：56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

文章讲解/视频讲解：https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html

思路

首先，对区间进行排序。如果有重叠区间，那么它们一定是连续的。

然后对每个区间进行遍历，每一次遍历的过程中，对区间取并集，如果当前区间不在之前的并集中，则
记录下并集区间，再开一个新的并集。与之前的无重叠区间相比，无重叠区间相当于在找交集。

C++实现

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        auto cmp = [](const vector<int>& a, const vector<int>& b){return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];};
        sort(intervals.begin(), intervals.end(), cmp);
        vector<vector<int>> results;

        int left = intervals[0][0];
        int maxRight = intervals[0][1];
        for(int i = 1;i<intervals.size();i++){
            if(intervals[i][0] <= maxRight){
                maxRight = max(maxRight, intervals[i][1]);
            }
            else{
                results.push_back({left, maxRight});
                left = intervals[i][0];
                maxRight = intervals[i][1];
            }
        }
        results.push_back({left, maxRight});
        return results;
    }
};