In this **Leetcode Minimum Number of Arrows to Burst Balloons problem solution** There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

## Problem solution in Python.

class Solution(object): def findMinArrowShots(self, points): if not points: return 0 points = sorted(points, key=lambda x:x[1]) count = 1 left = points[0][1] for i in points: if(i[0]>left): count += 1 left = i[1] return count

## Problem solution in Java.

class Solution { public int findMinArrowShots(int[][] points) { Arrays.sort(points, (a,b) -> Integer.compare(a[1], b[1])); int arrow = 1; int end = points[0][1]; for(int i = 1;i < points.length;i++){ if(points[i][0] > end){ arrow++; end = points[i][1]; } } return arrow; } }

## Problem solution in C++.

class Solution { static bool comp(vector<int> a,vector<int> b){ return a[1]<b[1]; } public: int findMinArrowShots(vector<vector<int>>& points) { if(points.size()==0) return 0; sort(points.begin(),points.end(),comp); int count = 1; int prev = points[0][1]; for(int i=0;i<points.size();i++){ if(points[i][0]>prev){ prev= points[i][1]; count++; } } return count; } };

## Problem solution in C.

int comp(const void*a,const void*b){ return ((int**)a)[0][1]-((int**)b)[0][1]; } int findMinArrowShots(int** points, int pointsRowSize, int pointsColSize) { qsort(points,pointsRowSize,sizeof(points[0]),comp); int i; int end; int arr=0; for(i=0;i<pointsRowSize;){ end=points[i][1]; while(++i<pointsRowSize&&points[i][0]<=end); arr++; } return arr; }

## 0 Comments