July 11, 2022 · 1 min read
https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
PQ of asc order end time, increase counter if next start >= current end
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(),points.end(), [&] (const vector<int> &a, const vector<int> &b) -> bool {
return a[1] < b[1];
});
int end = points[0][1];
int arrows = 1;
for(int i = 1; i < points.size(); i++) {
if(points[i][0] > end) {
arrows++;
end = points[i][1];
}
}
return arrows;
}
};