C++ day36 贪心算法无重叠区间划分字母区间合并区间

本文介绍: 一旦包含了某个字母，就不得不向后遍历，使得该字母只出现在这个区间里，寻找所有的该字母，最终将该片段分割，就是寻找该区间里所有字母的最远边界，这个边界就是分割点。还是先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，我还是按照左边界进行排序，然后考虑重叠的区间，移除数组中的元素，使得区间互不重叠，保证移除的元素数量最少，数组中至少包含一个元素。合并数组中的重叠区间，返回一个不重叠的区间数组，这个数组覆盖输入的所有区间。局部最优，使得重叠区间的个数最大，全局最优，移除最少的元素。

移除数组中的元素，使得区间互不重叠，保证移除的元素数量最少，数组中至少包含一个元素

局部最优，使得重叠区间的个数最大，全局最优，移除最少的元素

本题和昨天引爆气球的题目相似，还是对数组进行排序（按照左边界排序和右边界排序均可），这里还是选择的左边界排序

代码的精华所在

class Solution {
public:
    static bool cmp(const vector&lt;int&gt;&amp; a, vector&lt;int&gt;&amp; b){
        return a[0]&lt;b[0];//将左边界从小到大排序
    }
    int eraseOverlapIntervals(vector<vector<int&gt;&gt;&amp; intervals) {
        if(intervals.size()==0) return 0;
        //首先对数组的起始坐标进行从小到大排序
        sort(intervals.begin(),intervals.end(),cmp);
        int count=0;
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0]<intervals[i-1][1]){
                count++;
                //更新当前重叠区间的最小右边界
                intervals[i][1] = min(intervals[i][1],intervals[i-1][1]);
            }
        }
        return count;

    }
};

class Solution {
public:
    vector<int&gt; partitionLabels(string s) {
        int hash[27]= {0};
        for(int i=0;i<s.size();i++){
            hash[s[i]-'a'] = i;//求解字符串中每个字母出现的最远下标
        }
        int left=0,right = 0;//定义片段的左下标，右下标,计算片段的长度
        vector<int> result;
        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;

    }
};

class Solution {
public:
    static bool cmp(const vector<int>&amp; a, vector<int>&amp; b){
        return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>&amp; intervals) {
        if(intervals.size()==0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        vector<vector<int>> result ;
        result.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0]<=result.back()[1]){//重叠
                //左边界不用更新，因为左边界是按照从小到大排的
                //只更新右边界
                result.back()[1] = max(intervals[i][1],result.back()[1]);
                }
            else{//没有重叠
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};