算法整理——【贪心算法练习（3）区间问题】

本博客整理了一些用贪心算法解决的区间相关的题目。

一、用最少数量的箭引爆气球

题为，给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数 。

要用最少的弓箭引爆所有气球则我们需要射气球的重叠部分。贪心就体现在重复的就一起射穿。要计算重复的区间，我们需要定义cmp函数对数组进行排序。然后我们需要维护重叠区间的右边界，计算方式为目前重叠区间的右边界和下一个与之重复的区间的右边界中的最小值。

完整代码如下：

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b)
    {
        if(a[0]<b[0]) return 1;
        if(a[0]>b[0]) return 0;
        return a[1]<b[1];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        int num = 1;
        int right = points[0][1];
        for(int i = 1; i<points.size(); i++)
        {
            if(points[i][0]<=right)
            {
                right = min(points[i][1],right);
            }
            else
            {
                num++;
                right = points[i][1];
            }
        }
        return num;
    }
};

二、无重叠区间

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

跟上题思路是相同的，只是需要在出现重叠区间是计数。区间题目有的时候有些难以理解，我建议大家可以画线段图并结合例子加深理解。

完整代码如下：

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

三、划分字母区间

题目为，给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。返回一个表示每个字符串片段的长度的列表。

我们需要统计每个字符最远出现的位置。然后遍历字符串，记录目前区间的字符最远出现的位置的最大值，如果此时遍历到了目前的最大值，则说明可以在这里分割字符串，记录此刻区间长度即可。

完整代码及注释如下：

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> pos(27,0);
        //记录每个字母的最远的下标
        for(int i = 0; i<s.size();i++)
        {
            pos[s[i]-'a'] = i;
        }
        vector<int> ret;
        int left = 0;//区间左端点
        int right = 0;//区间右端点
        for(int i = 0; i<s.size(); i++)
        {
            right = max(right,pos[s[i]-'a']);
            if(right == i)
            {
                ret.push_back(i-left+1);
                left = i+1;
            }
        }
        return ret;
    }
};

说明：本文为作者整理知识点用于复习巩固，参考了代码随想录的讲解，有问题可以联系作者欢迎讨论~