总是会出现各自意外，让你不得不暂时停下手头上的事情。
1.用最少数量的箭引爆气球
就是有重叠区间的气球，一支箭就足以射掉，理解题目当时还懵了好一会儿
那么就有两个问题需要解决，一是什么时候需要两只箭，然后是怎么判断左右边界是否包括。
题目
452. 用最少数量的箭引爆气球
有一些球形气球贴在一堵用 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]。
示例 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]。
思路以及代码
代码随想录
为了让气球尽可能的重叠，需要对数组进行排序。
那么按照气球起始位置排序，还是按照气球终止位置排序呢？
其实都可以！只不过对应的遍历顺序不同，我就按照气球的起始位置排序了。
既然按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。
从前向后遍历遇到重叠的气球了怎么办？
如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。
以题目示例： [[10,16],[2,8],[1,6],[7,12]]为例，如图：（方便起见，已经排序）
可以看出首先第一组重叠气球，一定是需要一个箭，气球3，的左边界大于了 第一组重叠气球的最小右边界，所以再需要一支箭来射气球3了。
这里还要注意，cmp函数的使用，是对一个二维数组进行sort排序用的，static,const,&,不可缺。
class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>& b){return a[0]<b[0];}int findMinArrowShots(vector<vector<int>>& points) {if(points.size()==0) return 0;int result=1;sort(points.begin(),points.end(),cmp);for(int i=1;i<points.size();i++){if(points[i][0]>points[i-1][1]){result++;}else{points[i][1]=min(points[i-1][1],points[i][1]);}}return result;}
};2.无重叠子区间
这题其实思路跟弓箭很像，只是做的时候需要多加一些思考，尤其是更新最短右边那里。
题目
435. 无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。
示例 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 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
代码
class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>& b){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]){continue;}else{intervals[i][1]=min(intervals[i][1],intervals[i-1][1]);result++;}}return result;}
};3.划分字母区间
看似好像也是重叠子区间问题，但这题其实更加有难度，因为所涉及到的一些思想，很妙！
题目
763. 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = "eccbbbbdec" 输出：[10]
思路及代码
代码随想录
一想到分割字符串就想到了回溯，但本题其实不用回溯去暴力搜索。
题目要求同一字母最多出现在一个片段中，那么如何把同一个字母的都圈在同一个区间里呢？
如果没有接触过这种题目的话，还挺有难度的。
在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。
可以分为如下两步：
- 统计每一个字符最后出现的位置
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
如图：
class Solution {
public:vector<int> partitionLabels(string s) {int hash[27]={0};vector<int>result;for(int i=0;i<s.size();i++){hash[s[i]-'a']=i; //无敌思路，太牛}int left=0;int right=0;for(int i=0;i<s.size();i++){right=max(right,hash[s[i]-'a']); //也是妙极了的一步if(right==i){result.push_back(right-left+1);left=right+1;}}return result;}
};
)
