思路：看了眼题解，局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。如果真实的模拟射气球的过程，应该射一个，气球数组就remove一个元素，这样最直观，毕竟气球被射了。

但仔细思考一下就发现：如果把气球排序之后，从前到后遍历气球，被射过的气球仅仅跳过就行了，没有必要让气球数组remove气球，只要记录一下箭的数量就可以了。

	int findMinArrowShots(vector<vector<int>>& points) {int res = 1;sort(points.begin(), points.end());int preRight(points[0][1]);// for(auto i : points) {//     cout << i[0] << " " << i[1] << endl;// }// cout << "==========" << endl;for(int i = 1; i < points.size(); i++) {// cout << i << " " << preRight << endl;if(preRight < points[i][0]) {res++;preRight = points[i][1];} else {preRight = min(preRight, points[i][1]);}}return res;}

主要思路是每次都维护当前交集最小的边界，因为已经拍过序了。如果不相交，res++，然后更新当前位置能覆盖的最大边界，如果相交，就更新最小边界。和题解解法差不多

思路：
怎么看是否重叠？同样还是排序，看是否相交（left > right)
2. 有重叠移除哪个？移除右边界大的那个

	static bool cmp(const vector<int>& v1, const vector<int>& v2) {if(v1[0] == v2[0]) return v1[1] < v2[1];return v1[0] < v2[0];}
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);// for(auto i : intervals)//     cout << i[0] << " " << i[1] << endl;int res = 0;int preRight = intervals[0][1];for(int i = 1; i < intervals.size(); i++) {if(intervals[i][0] < preRight) {preRight = min(preRight, intervals[i][1]); // 有重叠移除大边界res++;} else {preRight = intervals[i][1]; // 无重叠更新边界}}return res;}

看了眼题解，思路差不多，我这里选用左边界排序

思路：整体思路和前两题差不多，区别在于，需要做转换。将同一字母划分在同一片段，遍历一次数组，保存字母出现的开始位置和结束位置，记录首字母位置信息，对保存的字母位置信息进行排序（排序是为了让开始位置连续，以便记录交集），若pre 和 cur 不相交，将之前的位置信息加入res中，更新新的左边界和右边界；相交，则更新边界

	static bool cmp(const vector<int>& v1, const vector<int>& v2) {if(v1[0] == v2[0]) return v1[1] < v2[1];return v1[0] < v2[0];}
public:vector<int> partitionLabels(string s) {vector<vector<int>> dp = {26, vector<int>{0, 0}};for(int i = 0; i < s.size(); i++) {int index = s[i]-'a';if(dp[index][0] == dp[index][1]) {dp[index][0] = i + 1;} else {dp[index][1] = i + 1;}}int preLeft = dp[s[0]-'a'][0];int preRight = dp[s[0]-'a'][1];sort(dp.begin(), dp.end(), cmp);vector<int> res;if(preRight == 0) preRight = preLeft;for(int i = 1; i < 26; i++) {if(dp[i][0] != 0) {if(dp[i][1] == 0) dp[i][1] = dp[i][0];// cout << (char)('a' + i) << " " << dp[i][0] << " " << dp[i][1] << endl;if(preRight >= dp[i][0]) {preRight = max(preRight, dp[i][1]);} else {// cout << "  " << preRight << " " << preLeft << endl;res.push_back(preRight - preLeft + 1);preLeft = dp[i][0];preRight = dp[i][1];}}}res.push_back(preRight - preLeft + 1);return res;}

看了下题解，还有另一种方法：
每一个字母都有其最远出现位置，如果在一个区间内，当前位置等于所有字母最远出现位置，那么说明到达了分界点，即可写出如下代码

	vector<int> partitionLabels(string s) {vector<int> res;int hash[26] = {0};for(int i = 0; i < s.size(); i++) {// hash[s[i]-'a'] = max(hash[s[i]-'a'], i);hash[s[i]-'a'] = i; // 记录最远位置}int right = 0; // 记录当前区间最远位置int left = 0;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 = right + 1;	}	}return res;}