Implement the minimumArrowsBalloons method that returns the minimum arrows needed to burst all balloons.
The input contains balloon ranges on a horizontal line. Each balloon is represented as [start, end].
An arrow shot at position x bursts every balloon whose range contains x. Your task is to return the minimum number of arrows needed to burst all balloons.
For example, [[10,16],[2,8],[1,6],[7,12]] can be burst using two arrows, so the answer is 2.
Example 1
Input
points (int[][]) =
[[10,16],[2,8],[1,6],[7,12]]size (int) =
4Returns (int)
2Example 2
Input
points (int[][]) =
[[1,2],[3,4],[5,6],[7,8]]size (int) =
4Returns (int)
4Example 3
Input
points (int[][]) =
[[1,2],[2,3],[3,4],[4,5]]size (int) =
4Returns (int)
2Use a greedy strategy based on balloon ending positions.
Sort the balloons by their end value. Shoot the first arrow at the end of the first balloon. Any later balloon whose start is less than or equal to this arrow position is already burst. When a balloon starts after the current arrow position, shoot a new arrow at that balloon end.
The number of arrows shot is the minimum required.
Pseudocode:
function minimumArrowsBalloons(points, size):
if size == 0:
return 0
sort points by end value ascending
arrows = 1
arrowPosition = points[0][1]
for i from 1 to size - 1:
if points[i][0] > arrowPosition:
arrows++
arrowPosition = points[i][1]
return arrowsReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run