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;
}
};
這題還蠻不錯的