Minimum Number of Arrows to Burst Balloons
Advertisement
Problem
Balloons are intervals [xstart, xend]. An arrow at x bursts all balloons containing x. Find minimum arrows.
Solutions
Python
class Solution:
def findMinArrowShots(self, points: list[list[int]]) -> int:
points.sort(key=lambda x:x[1])
arrows=0; pos=float('-inf')
for start,end in points:
if start>pos: arrows+=1; pos=end
return arrows
C++
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& p){
sort(p.begin(),p.end(),[](auto& a,auto& b){return a[1]<b[1];});
int arrows=0; long pos=LLONG_MIN;
for(auto& b:p){if(b[0]>pos){arrows++;pos=b[1];}}
return arrows;
}
};
Complexity
- Time: O(n log n) | Space: O(1)
Advertisement