代码随想录算法训练营第60期第三十四天打卡

       大家好，我们今天的内容依旧是贪心算法，我们上次的题目主要是围绕多维问题，那种时候我们需要分开讨论，不要一起并发进行很容易顾此失彼，那么我们今天的问题主要是重叠区间问题，又是一种全新的贪心算法思想，这里的题目如果我们之前没有接触过，我们就很难想到今天的解题思路，这里的题目我建议大家可以直接看题解，看完题解后多思考就可以了。

第一题对应力扣编号为452的题目用最少数量的箭引爆气球

        我们一起来看到这一道题目，这一道题目的话考察的应该是重叠区间问题，上面说过了这种思路不好想，那我们就一起来看看这道题目：

        题目其实读一遍大概就了解了我们题目的要求，我们在某一个位置射出弓箭，只要这个气球的直径的范围包含了我这个发射弓箭的位置那我们就可以引爆气球，很明显这是一个重叠区间问题，我们应该用一支弓箭引爆尽可能多的气球，我们一起来看一下这道题目的解题思路，首先局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。贪心算法可以解决这一道题目，

       大家来看我们的示例画出来的图，这是我们排好序的气球，如果把气球排序之后，从前到后遍历气球，被射过的气球仅仅跳过就行了，没有必要让气球数组remove气球，只要记录一下箭的数量就可以了。这里是按照气球的起始位置排序，这样我们就应该正序遍历，靠左尽可能让气球重复。如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。这个思想很重要大家可以看到上图，我们是不是要在有重合的气球的右边边界的最小值引一支弓箭，没有重叠的气球一定是不可能一支箭可以引爆的，根据上图可以看出首先第一组重叠气球，一定是需要一个箭，气球3，的左边界大于了 第一组重叠气球的最小右边界，所以再需要一支箭来射气球3了。根据这个思路我们可以尝试写出解题代码：

class Solution {
private:
//这个是我们按照气球的起始位置从小到大排序static bool cmp(const vector<int> &a , const vector<int> &b){return a[0] < b[0];}
public:int findMinArrowShots(vector<vector<int>>& points) {if (points.size() == 0) return 0;//排序sort(points.begin(), points.end(), cmp);int result = 1; // 只要有气球起码就得需要一直弓箭引爆for (int i = 1; i < points.size(); ++i){//这种情况需要一支箭 气球i和气球i-1不挨着 怎么得使用一直弓箭射爆//我需要解释一下这里为什么不加等于，大家看题目x_start <= x <= x_end就可以算作重叠可以引爆//也就是我下一个气球的左边界等于上一个气球的右边界的话也算作重叠 if (points[i][0] > points[i - 1][1]) result++;//更新右边界为什么要更新右边界这个大家注意我们是判断了两个气球是重合的但是与第三个气球是否重合呢？这就得需要更新右边界来比较//在遍历的过程中如果我发现目前的最小右边界与第三个气球的左边界不重合了说明我就用一支箭去射爆那两个气球else points[i][1] = min(points[i - 1][1], points[i][1]);}return result;}
};

       我给大家写出了详细的注释，大家好好理解，理解我们的区间重叠问题，我们什么时候可以确定我们的两个气球是否重叠，以及什么情况下需要一支新的弓箭，大家仔细理解，我们进入下一道题目。

第二题对应力扣编号为435的题目无重叠区间

       我们来到第二题，很明显一看题目名称我们就知道这应该还是区间重合问题，我们一起来看一下这道题目：

       这道题其实与上一道题目有异曲同工之妙，还是判断两个区间是否重合，但是有一点不一样，就是上一道题目我们如果边界相等的时候我们是可以视为重合的一支箭可以射爆，但这里如果只有一个点重合不能算作是重叠，我们来看一下这道题应该如何解决，我这里给大家讲解我们排序左边界的情况，当然我也给出右边界的情况大家视情况而定，其实左边界我个人感觉比较好理解，主要上一道题我们也是排序的左边界，我们依旧是判断两个区间是否重叠 ，大家注意这里的不重叠的条件是下一个区间的左边界大于等于上一个区间的有边界才是，如果重叠了我们统计重叠的区间，然后更新右边界来判断后续区间是否还是重叠的，大家上一道题目理解的话这道题就不难了，我给出左边界的代码：

class Solution {
private:
//按照左边界排序static bool cmp(const vector<int> &a , const vector<int> &b){return a[0] < b[0];}
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) return 0;//按照特定规则排序sort(intervals.begin(), intervals.end(), cmp);int count = 0; //统计重叠区间的个数int end = intervals[0][1];for (int i = 1; i < intervals.size(); ++i){//表示上来的两个区间并不重合//我们就更新右边界无需操作反正都是不重叠的if (intervals[i][0] >= end) end = intervals[i][1];//这里是重叠else{//更新最小的右边界end = min(intervals[i][1], end);count++;} }return count;}
};

     我也给出右边界的代码供大家参考：

class Solution {
public:// 按照区间右边界排序static bool cmp (const vector<int>& a, const vector<int>& b) {return a[1] < b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count = 1; // 记录非交叉区间的个数int end = intervals[0][1]; // 记录区间分割点for (int i = 1; i < intervals.size(); i++) {if (end <= intervals[i][0]) {end = intervals[i][1];count++;}}return intervals.size() - count;}
};

    这道题目就讲解到这里，我们继续进入下一道题目。

第三题对应力扣编号为763的题目划分字母区间

        我们来到今天的最后一题，我相信只要大家把这三道题目弄明白几乎重叠区间问题大家就会有很清楚的了解了，我们一起来看一下今天的最后一道题目：

        题目是什么意思呢？我们要划分为尽可能多的片段，使得原字符串里面的每一个字符都出现在划分好的一个字符串里，而且还不能打乱顺序，使得这些划分好的字符串拼起来还是原字符串，我们需要划分的片段尽可能多，那么应该如何考虑这个问题呢？其实有些朋友可能会觉得这题奇怪我们原则上应该都是求尽可能少的情况，但是这里大家一想你要尽可能少直接不要划分了不就是了，这样肯定题目只能问尽可能多，拿示例一来举例，我出现了字符a,那么我所有的a都要包含进来，我们统计我们a出现的最远位置下标，然后统计过程中b又出现了所以b只能与a分割在一个字符串里面了，然后后来c也出现了我的字符串中，因此c只能与a,b分割在同一个字符串中，最后我们发现a的最远位置就是第一个字符串的长度，接下来e也是一样的道理，还有h都是一样的道理，我们就可以发现我们是需要求出我们每一个字符的最远出现位置的下标，然后我们去求每一个区间长度的时候我们就得用双指针了，然后我们求完一个区间长度我们保存到数组里面，我们讲下一个区间的起始索引交给左指针，最后我们返回result就可以了，我们有了这个思路一起来看一下代码应该如何写：

class Solution {
public:vector<int> partitionLabels(string s) {//统计每一个字符的最远出现位置int hash[27] = {0};//如何统计最远出现距离大家注意我的i一直在动这样可以找出最远出现的位置的下标for (int i = 0; i < s.size(); ++i){hash[s[i] - 'a'] = i;}int left = 0, right = 0;vector<int> result;//这个大家要注意eccbbbbdec举例 hash[2] = 9(c) hash[1] = 6(b) hash[4] = 8(e) hash[3] = 7(d)// right = 8 right = 9 right = 6 right = 7 right = 8 right = 9 到了最后才会满足i == right//我们i == right 就是在寻找区间分界线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;}
};

       我给大家写好了注释，大家参考一下。

今日总结

          今天的区间重叠问题还是很有趣的，体现了贪心的思想，我们到底是按照左边还是右边排序，这个大家都要思考清楚才可以，今天的分享就到这里了，我们下次再见！