Given balloons as horizontal segments on a number line, the machine must fire vertical arrows from the x-axis so that every balloon is burst. An arrow fired at coordinate x bursts every balloon whose segment contains x, and the machine must minimize the number of arrows.
The key insight is that this is interval scheduling in disguise: one arrow can cover a set of balloons exactly when their segments share at least one common x. Firing at the earliest balloon's right endpoint is always optimal, because that point is guaranteed to be inside any overlapping balloon that shares the segment.
The approach runs in three steps. First, sort the segments by their right endpoint. Second, fire the first arrow at the first balloon's end and count it. Third, walk the rest: any balloon whose start is at or before the arrow's position is already burst, and any balloon starting beyond it forces a new arrow at its own end. Time is O(n log n) and space is O(1).
The trickiest edge case is inclusive endpoints: segments that touch at a single point, like [1,2] and [2,3], can be burst by one arrow at x = 2. The comparison must be start > arrow position to trigger a new arrow, not start >=, otherwise the machine wastes an arrow on touching balloons.
def findMinArrowShots(points):
points.sort(key=lambda x: x[1])
arrows, last = 1, points[0][1]
for start, end in points[1:]:
if start > last:
arrows += 1
last = end
return arrows