# 用最少的箭引爆气球

题目链接🔗

局部最优：当气球出现重叠，一起射，所用弓箭最少。

全局最优：把所有气球射爆所用弓箭最少。

为了让气球尽可能的重叠，需要对数组进行排序。

按照起始位置排序，从前向后遍历气球数组，靠左尽可能让气球重复。

如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。

	class Solution {
	private:
	static bool cmp(const vector<int>& a, const vector<int>& b) {
	return a[0] < b[0];
	}
	public:
	int findMinArrowShots(vector<vector<int>>& points) {
	if (points.size() == 0) return 0;
	sort(points.begin(), points.end(), cmp);

	int result = 1; //points 不为空至少需要一支箭
	for (int i = 1; i < points.size(); i++) {
	if (points[i][0] > points[i - 1][1]) { // 气球 i 和气球 i-1 不挨着，注意这里不是 >=
	result++; // 需要一支箭
	}
	else { // 气球 i 和气球 i-1 挨着
	points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
	}
	}
	return result;
	}
	};

# 无重叠区间

题目链接🔗

将区间都按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是要移除的区间个数。

Alt text

当确定 区间1 和 区间2 重叠后，取两区间右边界最小值，如果这个最小值也和 区间3 重叠，就说明三个区间重叠。

	class Solution {
	public:
	// 按照区间右边界排序
	static bool cmp (const vector<int>& a, const vector<int>& b) {
	return a[1] < b[1];
	}
	int eraseOverlapIntervals(vector<vector<int>>& intervals) {
	if (intervals.size() == 0) return 0;
	sort(intervals.begin(), intervals.end(), cmp);
	int count = 1; // 记录非交叉区间的个数
	for (int i = 1; i < intervals.size(); i++) {
	if (end > intervals[i][0]) {
	end = intervals[i][1];
	count++;
	}
	}
	return intervals.size() - count;
	}
	};

题目链接🔗

在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

可以分为如下两步：

Alt text

	class Solution {
	public:
	vector<int> partitionLabels(string S) {
	int hash[27] = {0}; //i 为字符，hash [i] 为字符出现的最后位置
	for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置
	hash[S[i] - 'a'] = i;
	}
	vector<int> result;
	int left = 0;
	int 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 = i + 1;
	}
	}
	return result;
	}
	};

题目链接🔗

先排序，让所有相邻区间重叠在一起。

按左边界从小到大排序后，如果 intervals[i][0] <= [intervals[i-1][1] ，则重叠。

合并区间就是用合并区间后左边界和右边界，作为一个新的区间，加入到 result 数组里就可以了。如果没有合并就把原区间加入到 result 数组。

	class Solution {
	public:
	vector<vector<int>> merge(vector<vector<int>>& intervals) {
	vector<vector<int>> result;
	if (intervals.size() == 0) return result; // 区间集合为空直接返回
	// 排序的参数使用了 lambda 表达式
	sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});

	// 第一个区间就可以放进结果集里，后面如果重叠，在 result 上直接合并
	result.push_back(intervals[0]);

	for (int i = 1; i < intervals.size(); i++) {
	if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间
	// 合并区间，只更新右边界就好，因为 result.back () 的左边界一定是最小值，因为我们按照左边界排序的
	result.back()[1] = max(result.back()[1], intervals[i][1]);
	} else {
	result.push_back(intervals[i]); // 区间不重叠
	}
	}
	return result;
	}
	};