用最少数量的箭引爆气球
有一些球形气球贴在一堵用 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]。提示:
1 <= points.length <= 105points[i].length == 2-231 <= xstart < xend <= 231 - 1
先对points排序，要自己先写一个排序函数，以气球的左位置进行排序，从小到大。
先判断size是否为0 ，如果为0，return 0即可。
其次在循环内判断end与points[i][0]的关系，如果end< points[i][0],即二者不重叠，那么就可以让result++；如果不是，就让end等于min（end，points[i][1]）。
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;
sort(points.begin(),points.end(),cmp);
int result = 1;
int end = points[0][1];
for(int i = 1;i<points.size();i++)
{
if(points[i][0]>end)
{
result++;
end = points[i][1];
}
else
end = min(end,points[i][1]);
}
return result;
}
};无重叠区间
给定一个区间的集合
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 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。提示:
1 <= intervals.length <= 105intervals[i].length == 2-5 * 104 <= starti < endi <= 5 * 104
本题左右边界排序都可以，这里只考虑左边界排序的情况。
在循环内，每次判断end与intervals[i][0]去比较，重合的话，就让result++，考虑让end变为二者（原end和intervals[i][1]）中更小的；如果不重合的话，就end就等于intervals[i][0]。
本题与上题的情况正好相反，这个是重合更多，结果更小；上题是重合更多，结果更小。
class Solution {
public:
static bool cmp(const vector<int>& a,const 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;
sort(intervals.begin(),intervals.end(),cmp);
int result = 0;
int end = intervals[0][1];
for(int i = 1;i<intervals.size();i++)
{
if(end>intervals[i][0])
{
result++;
end = min(intervals[i][1],end);
}
else
{
end = intervals[i][1];
}
}
return result;
}
};划分字母区间
给你一个字符串
s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串"ababcc"能够被分为["abab", "cc"]，但类似["aba", "bcc"]或["ab", "ab", "cc"]的划分是非法的。注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是
s。返回一个表示每个字符串片段的长度的列表。
示例 1：输入：s = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。示例 2：
输入：s = "eccbbbbdec" 输出：[10]提示：
1 <= s.length <= 500s仅由小写英文字母组成
先用数组做一个哈希表，记录每一个字母最后一次出现的位置。
遍历s数组，令end 等于原end和hash[s[i]-'a']的最大值。如果i== end 就记录一次区间大小（end-start+1），然后让start = end +1.
class Solution {
public:
vector<int> partitionLabels(string s) {
vector<int> hash(27,-1);
vector<int> result;
if(s.size()==0) return result;
for(int i = 0;i<s.size();i++)
{
hash[s[i]-'a'] = i;
}
int start = 0;
int end = 0;
for(int i= 0;i<s.size();i++)
{
end = max(end,hash[s[i]-'a']);
if(i == end)
{
result.push_back(end - start +1);
start = end + 1;
}
}
return result;
}
};今天的三道题重叠度很高，关键要考虑边界的最大值，未必就是新节点的边界，还需要考虑原节点的边界和新节点的边界的位置关系。
还有就是sort函数的写法，自己创建的数组排序时，要自己写排序逻辑。