Minimum Number of Arrows to Burst Balloons
There are some spherical balloons spread out in the XY-plane.
Each balloon is represented by an interval [xstart, xend], where xstart and xend represent the horizontal diameter of the balloon.
An arrow can be shot vertically upward from different points along the x-axis.
A balloon with coordinates [xstart, xend] is burst if the arrow is shot at a point x where xstart <= x <= xend.
There is no limit to the number of arrows that can be shot.
Return the minimum number of arrows that must be shot to burst all balloons.
Example 1
Input
4 10 16 2 8 1 6 7 12
Output
2
Explanation
An arrow shot at x = 6 bursts [2,8] and [1,6].
Another arrow shot at x = 11 bursts [10,16] and [7,12].
Therefore, the minimum number of arrows is 2.
Example 2
Input
4 1 2 3 4 5 6 7 8
Output
4
Explanation
None of the balloons overlap, so each balloon requires its own arrow.
Example 3
Input
4 1 2 2 3 3 4 4 5
Output
2
Explanation
An arrow at x = 2 bursts [1,2] and [2,3].
An arrow at x = 4 bursts [3,4] and [4,5].
Constraints
Hints:
Hint 1
Sort the balloons by their ending points.
Hint 2
Shoot an arrow at the end of the first balloon. If the next balloon starts after that position, another arrow is required.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 9, 2026
Last updated
Aug 10, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output