Fewest Laser Shots to Pop Every Balloon
Implement fewestShots
Balloons are stuck to a wall, each covering a horizontal stretch from xStart to xEnd. A laser shot is a vertical line at some position x: it pops every balloon whose stretch contains x, ends included, and keeps going. Find the fewest shots that pop every balloon.
Trying combinations of shot positions is exponential. But sorting the balloons by right end reveals a simple rule: the first unpopped balloon must be hit, and the best place to hit it is at its right end, which also pops every balloon that starts at or before that position.
Example 1:
Input: balloons = [[3,9],[1,4],[6,10],[12,15],[8,12],[2,5]]
Output: 3
Example 2:
Input: balloons = [[1,3],[3,5]]
Output: 1
Example 3:
Input: balloons = [[1,2],[4,5],[7,8]]
Output: 3
+ 9 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ balloons.length ≤ 10; each balloon is [xStart, xEnd] with 0 ≤ xStart ≤ xEnd ≤ 50, the horizontal stretch it covers on a wall - ●
A shot is a vertical laser at some x (any integer or real position); it pops every balloon with xStart ≤ x ≤ xEnd — the ends count as inside - ●
A shot passes through all balloons at that x, and popped balloons do not stop it - ●
Return the fewest shots needed to pop every balloon
balloons =