There are some spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter, and hence the x-coordinates of start and end of the diameter suffice. The start is always smaller than the end.
An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps traveling up infinitely.
Given an array points where points[i] = [xstart, xend], return the minimum number of arrows that must be shot to burst all balloons.
Example 1:
Input: points = [[10,16],[2,8],[1,6],[7,12]] Output: 2 Explanation: One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).
Example 2:
Input: points = [[1,2],[3,4],[5,6],[7,8]] Output: 4
Example 3:
Input: points = [[1,2],[2,3],[3,4],[4,5]] Output: 2
Example 4:
Input: points = [[1,2]] Output: 1
Example 5:
Input: points = [[2,3],[2,3]] Output: 1
Constraints:
0 <= points.length <= 10^4points[i].length == 2-2^31 <= xstart < xend <= 2^31 - 1
The description was taken from https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/.
#O(N(Log N)) Time, O(N) Space used in Sortingclass Solution: def findMinArrowShots(self, points: List[List[int]]) -> int: points.sort(key = lambda x: x[1]) count = 0 end = float('-inf') for i in range(0, len(points)): if points[i][0] > end: count += 1 end = points[i][1] return countThe description says that we need to "find the minimum number of arrows that must be shot to burst all balloons".
When we see buzz sentences like "find the minimum number of x to y", or "find the maximum number of x that is y", a greedy approach may be the way to go.
This makes sense though right? If we were a greedy carnival game player, we would want to make the best plan to win the most from the game by using the fewest arrows possible so that we can still have more chances to win.
For example, let's say we have these balloons input: [[10,16],[2,8],[1,6],[7,12]].
The width would span like this shown below, except obviously they would be more spherical.
We could capitalize on arrows if we were to sort these by end times to get overlapping balloons that we can pop with a single arrow.
Now look at that, we could shoot an arrow up from six to hit the green and blue balloons, then we could shoot an arrow up from ten to hit the purple and red balloons.
That would also hold true for the former grouping for this specific example, but this grouping will benefit us regardless because when we count arrows we will know that unless we have another balloon that starts after a previous one ends, meaning the start value is greater, that it can be popped along with a previous balloon.
We will start off by sorting the intervals by their ending positions.
points.sort(key = lambda x: x[1])
Then, we will initialize our arrow count and the end position.
count = 0 end = float('-inf')
For each balloon, the end value will be compared against future balloon span intervals. If another balloon ends less than or equal to this value, then that balloon can be popped along with a previous balloon(s) that also end before or at the same time.
If it doesn't, then it will become the new endpoint that we are focused on grouping balloons at or before.
We will also need another arrow because this current balloon can't be popped along with any previous ones.
for i in range(0, len(points)): if points[i][0] > end: count += 1 end = points[i][1]
Once we have seen the minimum number of arrows we need to pop all of the balloons, we will return the count.
return count