贪心算法day30|452. 用最少数量的箭引爆气球(排序+多重叠的处理)、435. 无重叠区间（去除哪个才是最优）、763. 划分字母区间（类阿斯克码换算）

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

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

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

给你一个数组 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]。

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

提示:

• 1 <= points.length <= 105
• points[i].length == 2
• -231 <= xstart < xend <= 231 - 1

一开始写的类似于暴力解法，但是处理补不了2个以上区间重叠的情况。看了卡哥的思路之后，写出的代码如下：

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 result=1;for(int i=1;i<points.size();i++){if(points[i-1][1]<points[i][0])result++;elsepoints[i][1]=min(points[i][1],points[i-1][1]);}return result;}
};

核心思路：重叠，result不变；不重叠，result加一

难点：

• 排序（O(nlogn)）,首先按照左边界递增排序。这招化腐朽为神奇，非常巧妙，但是很难想到。

• 对于多重叠的处理：对于重叠的情况，重新界定最小右边界，即：

points[i][1]=min(points[i][1],points[i-1][1]);

这在本次循环里面不起作用，而是在下一次循环里起作用，这是一种**整体性思维，**高级的迭代

• 分两种情况，如果前一个不是重叠区间，则直接比；如果前一个是重叠区间，看起来是也是直接比，但实际上是和重叠区间整体的最小右区间比

易错点：

• **初始时result=1;**在初始的时候默认射一支箭，然后后面重叠了就不用变了，不重叠才需要继续加一，这是按照我们整体的思维来的
• 当初始result=1时，必须剪掉个数为0的情况，因为result=1在这种情况下不满足，所以需要单独考虑，即：

if(points.size()==0)return 0;

435. 无重叠区间

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

示例 1:

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

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

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

这题我一开始时思考的是当出现重叠时，去除哪一个才能达到局部最优？其实这种想法是错的，当我们排序之后，其实已经把这些问题梳理清楚了，此时我们只需要确定有几个重叠区间就行了，不用再考虑去除哪个才是最优。因为这些区间的互相影响关系已经通过排序很清晰地给出了。

763. 划分字母区间

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

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

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

示例 1：

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

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

class Solution {
public:vector<int> partitionLabels(string s) {int hash[26];vector<int> result;for (int i = 0; i < s.size(); i++) {hash[s[i] - 'a'] = i;}int left = 0, 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 = right + 1;}}return result;}
};

核心思路：记录每个字母出现的最大下标，然后根据最大下标所划分的区间，利用双指针来获取。

每个部分都是难点：

• 记录每个字母出现的最大下标

int hash[26];for (int i = 0; i < s.size(); i++) {hash[s[i] - 'a'] = i;

有点类似于字母的阿斯克码的换算。

• 双指针左闭右闭限定空间，取最大下标处为right；当i==right时这个区间截止。

 right = max(right, hash[s[i] - 'a']);if (i == right) {result.push_back(right - left + 1);left = right + 1;}