【算法day24】贪心：重叠区间

题目引用

用最少数量的箭引爆气球
无重叠区间
划分字母区间(类贪心)

1.用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。

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

示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

我们来分析一下题目，题目要求我们最少的数量射到最多的气球，那么我们本能的反应就是能不能一箭双雕或者一箭n雕。这也就是局部最优，只要我们一直保持这个策略，那么逐步递推我们就能得到全局最优。但其中是有一些细节我们需要注意的，比如说我们找到了重叠的区间，那么我们就要把较靠后的气球的右边界改为重叠区间的右边界，这样才能最大程度上一箭n雕，如果区间不重叠，那么我们就要将箭数+1。
来看代码：

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

是不是很顺就写出来啦~

2. 无重叠区间

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

注意只在一点上接触的区间是不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

我们来看一下这道题，实际上是跟昨天的一道题目很像的，但是贪心就是这样，一句话不一样，整道题都是另外一个思路。首先我们来看，我们要找到没有重叠的区间的个数，然后返回移除掉重叠区间的个数，那么移除重叠区间的个数=总区间个数-不重叠区间个数。那么我们就要开始排序了，这里采用右边界进行排序，原因也很简单，如果利用左边界进行排序的话我们还要额外判断右边界是否发生重叠，更麻烦了一些，所以我们用右边界排序。那么怎么找无重叠区间呢，我们创建一个end令它等于第一个区间的右边界，只要有区间的左边界不等于它，它就等于这个区间的右边界，并使无重叠区间的数量++。那么这道题就做出来啦
来看代码：

class Solution {
public:static bool cmp(vector<int>& a,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;}
};

3. 划分字母区间

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

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

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

示例 1：
输入：s = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。

因为这题跟贪心其实不是很像，但是做题方法是比较巧妙的所以我们来看一下吧。
这道题目其实可以用回溯来做，但是我们这里还有其他解法，我们用一个数组作为哈希表来标记字母最远的出现位置，然后通过遍历不断更新它，过程中定义一个变量right表示最远距离只要right等于当前位置i，那么就说明到达最远位置了，将结果入到结果数组中，最后返回结果就好啦。

lass Solution {
public:vector<int> partitionLabels(string S) {int hash[27] = {0}; // i为字符，hash[i]为字符出现的最后位置for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置hash[S[i] - 'a'] = i;}vector<int> result;int left = 0;int 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;}
};