Coding Practice: Minimum Number of Arrows to Burst Balloons
January 6, 2023
Problem
Example 1:
Input: points = [[10,16],[2,8],[1,6],[7,12]]Output: 2Explanation: The balloons can be burst by 2 arrows:- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].
Solution
Step 1
Create implementation custom type Points
to create custom sort with provide Len() int
, Swap(i, j int)
, and Less(i, j int) bool
. See the example (opens in a new tab) from sort package documentation for more details
Step 2
Type cast [][]int
to Points
then check if intervals is empty return 0
.
Step 3
Sort the intervals values. Keep in mind make sure import package sort
first if trying in local computer, because in the leetcode editor is already imported.
Step 4
Iterate through the sorted array and keep track of the rightmost end point of a burst balloon
Step 5
When we encounter a new balloon, if its start x-coordinate
is less than or equal to the rightmost end point, we don't need to shoot a new arrow as the current arrow will burst the new balloon as well.
Step 6
If the start x-coordinate
is greater than the rightmost end point, we need to shoot a new arrow and update the rightmost end point to be the end x-coordinate
of the new balloon. This way, we can determine the minimum number of arrows needed to burst all the balloons.
Step 7
This way, we can determine the minimum number of arrows needed to burst all the balloons.
Step 1
Create implementation custom type Points
to create custom sort with provide Len() int
, Swap(i, j int)
, and Less(i, j int) bool
. See the example (opens in a new tab) from sort package documentation for more details
Step 3
Sort the intervals values. Keep in mind make sure import package sort
first if trying in local computer, because in the leetcode editor is already imported.
Step 5
When we encounter a new balloon, if its start x-coordinate
is less than or equal to the rightmost end point, we don't need to shoot a new arrow as the current arrow will burst the new balloon as well.