There are many spherical balloons in two-dimensional space . For each balloon , The input provided is in the horizontal direction , The start and end coordinates of the balloon diameter . Because it's horizontal , So the ordinate doesn't matter , So just knowing the abscissa of the beginning and the end is enough . The start coordinate is always less than the end coordinate .
A bow and arrow can follow x The axis shoots out completely perpendicular from different points . In coordinates x Shoot an arrow at , If there is a balloon with a diameter starting and ending coordinates of x s t a r t , x e n d x_{start},x_{end} xstart,xend, And meet x s t a r t , ≤ x ≤ x e n d x_{start},≤ x ≤ x_{end} xstart,≤x≤xend, Then the balloon will explode . There is no limit to the number of bows and arrows that can be shot . Once the bow is shot , Can move forward indefinitely . We want to find out how to make all the balloons explode , The minimum number of bows required .
Give you an array points , among p o i n t s [ i ] = [ x s t a r t , x e n d ] points [i] = [x_{start},x_{end}] points[i]=[xstart,xend], Return to the minimum number of bows and arrows that must be fired to detonate all balloons .
Consider the one with the leftmost right boundary of all balloons , Then there must be an arrow whose shooting position is its right boundary （ Otherwise, no arrow can detonate it ）. When we identify an arrow , We can remove all the balloons detonated by this arrow , And from the remaining unexploded balloons , And then select the one on the left of the right boundary , Determine the next arrow , Until all the balloons were blown up .
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
# First step , First, perform a sort operation on the original array , Sort right end
points.sort(key = lambda x:x[1])
# The smallest ball on the right
pos = points[0][1]
# Note that initialization is 1, Because any needle can shoot a balloon
ans = 1
for p in points:
# If the left boundary of a balloon is within the smallest right boundary , Then the balloon can be shot to
if p[0]>pos:
# Update the smallest right boundary
pos = p[1]
ans +=1
return ans
