452. 用最少数量的箭引爆气球
1.按气球前端排序
虽然过了但是很慢QAQ
class Solution {
public:
int findMinArrowShots(vector<vector<int>> &points) {
if (points.size() == 0)
return 0;
sort(points.begin(), points.end(),
[](vector<int> x, vector<int> y) { return x[0] < y[0]; });
int res = 1;
int begin = points[0][0];
int end = points[0][1];
for (int i = 1; i < points.size(); i++) {
if (end >= points[i][0]) {
begin = points[i][0];
end = min(end, points[i][1]);
} else {
res++;
begin = points[i][0];
end = points[i][1];
}
}
return res;
}
};
2.按气球后端排序
大佬的代码简洁又快QAQ，前面sync_with_stdio那个是关同步，提高cin速度。具体可以参考 解析static auto x = []() { std::ios::sync_with_stdi..._CSDN博客
大佬的代码
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) return 0;
sort(points.begin(), points.end(), [](const auto& l, const auto& r)
{
return l[1] < r[1];
});
int count = 1;
int tail = points[0][1];
for (int i = 1; i < points.size(); i++)
{
if (points[i][0] <= tail) continue;
count += 1;
tail = points[i][1];
}
return count;
}
};
一开始感觉贪心简单。。现在感觉贪心对脑子要求很高QAQ
