Minimum Number of Arrows to Burst Balloons

Sanjeev SharmaSanjeev Sharma
1 min read

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

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro