代码随想录算法训练营第三十天|查找重叠区间、划分字母区间
用最少数量的箭引爆气球 leetcode 452
首先对数组按照左边界从小到大排序，遍历数组，判断当前气球的左边界是否与上一个气球的右边界有重合，如果没有箭数加一，如果有则更新当前气球右边界（取当前气球与上一个气球右边界的最小值）。难点就在于判断当前气球与上一个气球重叠之后，怎么判断下一个气球与当前气球是否重叠，就需要更新气球右边界。
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) {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],points[i-1][1]);}return res;}
};无重叠区间 leetcode 435
本题和上一题类似都是找重叠区间，不同的是对结果的++，上一题是遇到不重叠的++，本题是遇到重叠的++。
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) {sort(intervals.begin(),intervals.end(),cmp);int res=0;for(int i=1;i<intervals.size();i++){if(intervals[i][0]<intervals[i-1][1]) {res++;intervals[i][1]=min(intervals[i][1],intervals[i-1][1]);}}return res;}
};划分字母区间 leetcode 763
首先记录每一个字母出现的最远距离，然后便利字符串不断用当前字母出现最远距离更新右边界，直到右边界等于当前遍历位置，存结果，更新左边界继续向后遍历。
lass Solution {
public:vector<int> partitionLabels(string s) {int hash[27]={0};for(int i=0;i<s.size();i++){ //记录每一个字母出现的最远距离hash[s[i]-'a']=i; }int left=0,right=0;vector<int> res;for(int i=0;i<s.size();i++){right=max(right,hash[s[i]-'a']);if(i==right){res.push_back(right-left+1);left=i+1;}}return res;}
};