Each balloon covers an interval on the x axis. A vertical arrow at x bursts every balloon that covers x, so find the fewest arrows to burst them all.
DSA Animator › DSA Revision › Intervals › Minimum Number of Arrows to Burst Balloons
Remember: sort by end, and shoot at the end. One arrow covers every balloon that starts before it. The video solves Minimum Number of Arrows to Burst Balloons (LeetCode 452, Medium) with the Greedy by End pattern from the Intervals topic, and you can replay every step in the interactive Minimum Number of Arrows to Burst Balloons animation.
Each balloon covers an interval on the x axis. A vertical arrow at x bursts every balloon that covers x, so find the fewest arrows to burst them all.
For 10 to 16, 2 to 8, 1 to 6 and 7 to 12, two arrows are enough, at 6 and at 12.
Trying arrow positions everywhere is far too slow. Shooting at the end of a balloon hits the most others.
Sort the balloons by their end. Shoot an arrow at the end of the first balloon that is still whole. Every balloon that starts at or before that point bursts too.
Sorted by end: 1 to 6, 2 to 8, 7 to 12, 10 to 16. Shoot at 6, which bursts 1 to 6 and 2 to 8. 7 to 12 starts after 6, so shoot again at 12. That bursts 7 to 12 and 10 to 16. Two arrows burst all the balloons.
In code, sort by the end value. Shoot the first arrow at the first end. For each balloon that starts after the arrow, add an arrow at its end. It's O of n log n time.
Remember: sort by end, and shoot at the end. One arrow covers every balloon that starts before it.