[Top Interview 150] 452. Minimum Number of Arrows to Burst Balloons

Solution)

 

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        # Initialization
        points.sort()
        res = [points[0]]

        for start, end in points[1:]:
            # If the cur interval and prev interval overlap
            # find the part that only overlaps with no leftover
            if start <= res[-1][1]:
                res[-1][0] = start
                res[-1][1] = min(res[-1][1], end)
            
            # IF the intervals don't overlap
            else:
                res.append([start, end])
        
        return len(res)

 
 
Problem: LeetCode
 
Time Complexity: O(n logn)
Space Complexity: O(n)
 
 

Explanation)
 

We'll first sort points.
 
Then as we iterate, we'll merge overlapping intervals in points. However, we'll merge them so that the merged interval only includes the part that overlaps.
 
For example, if we have [1, 4] and [3, 7], instead of merging them into [1, 7] we'll merge them into [3, 4] which is the only part that overlaps.
 
Then we append the merged intervals into res and return the length of res as the length represents the minimum number of arrows.
 
 

Initialization)
 

We'll sort points.
res will be a list that will save the merged intervals. It will initially have the 0th interval as we're given at least 1 interval.
 

def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort()
        res = [points[0]]

 
 

Merge intervals)
 

We'll iterate points from its 1st interval.
 
If we find that start is less than res[-1][1] we know that the current interval and the previous interval overlap.
 
Since we only want the part that overlaps, our new merged interval's

1. start needs to be max(res[-1][0], start)
2. end needs to be max(res[-1][1], end)

We already know that max(res[-1][0], start) will always be start because points is already sorted. So we only need to use min() function for res[-1][1].
 
If our current interval doesn't overlap with the previous interval, we simply append the current interval.
 
 
Once we appended all the merged intervals, we now have the minimum number of arrows which is the length of res. For each interval in res, we only need a minimum of 1 arrow.
 

def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort()
        res = [points[0]]

        for start, end in points[1:]:
            if start <= res[-1][1]:
                res[-1][0] = start
                res[-1][1] = min(res[-1][1], end)
            else:
                res.append([start, end])
         
        return len(res)

 
 
 
I'm glad that I was able to solve an interval problem without NeetCode. There was a very clever solution by another user, so I recommend checking this as well.