452. Minimum Number of Arrows to Burst Balloons
今天的题目蛮有水准的，我觉得很值得写
方法很容易想，要证明却不是很容易
给你一堆区间，[x_{start}, x_{end}], ...
要你找出一组 a_1, ..., a_n 使得每个区间都包含至少一个点
问所需最少的点的数量
直觉上就是要找出最长的不重叠区间序列
剩下的是证明这是最佳解
首先，很明显最佳解一定 >= 这个序列的长度
因为两两都不重叠，一个点最多对应到一个区间
答案不可能比这还要好
剩下的是去证最佳解 <= 这个序列的长度
也就是真的能建构出一组和这个序列一样长的解
老实说我想了一阵子也不知道怎么证
后来发现从我实作最长不重叠区间的算法来证的话变得很容易
先对右端点做排序，接着对每一个新的区间
如果加入后不会重叠就加入，否则舍弃
我发现如果不断将点设在加入的区间的最右端
因为被舍弃掉代表他包含了某个我们加入的区间的右端点
自然而然最后的结果是一组合法的解
再根据之前说的，答案不可能比最长不重叠序列好
所以最佳解不多不少就是最长不重叠序列
至于这个算法的结果为什么是最长不重叠区间
我们可以证明，考虑完一个新的区间之后的结果都是有最小右端点的最佳解
对于一个新的区间，有两种可能，加入或不加入
如果跟原本的解不重叠当然加入一定是当下唯一的最佳解
如果重叠的话，因为目前的答案是有最小右端点的最佳解
因此所有最佳解都一定和新的点重叠，加入一定不会比较好，可以直接舍弃
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
using T = pair<int, int>;
sort(points.begin(), points.end(), [](const auto& x, const auto& y){
return T{x[1], x[0]} < T{y[1], y[0]};
});
int ans = 0;
int64_t prev = numeric_limits<int64_t>::min();
for (auto& p: points) {
int st = p[0], ed = p[1];
if (st <= prev) continue;
prev = ed;
ans += 1;
}
return ans;
}
};
这题还蛮不错的