452. Minimum Number of Arrows to Burst Balloons

[fockspaces]

when trying to find min / max / most... we can first think of it as a greedy problem. if the window is overlapped cur_point[1] >= new_point[1], we can shot both ballon at once.

If they're overlapped, we can further compare whther the new one can overlapped both old twos. We can make this by simplify update the cur_point[1] to the smallest Xend of the both, if new one overlapped with the tail of more left one, it must overlapped with the other.

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort()
        cur_point, ans = points[0], 1
        for i in range(1, len(points)):
            new_point = points[i]
            if cur_point[1] >= new_point[0]:
                cur_point[1] = min(cur_point[1], new_point[1])
            else:
                ans += 1
                cur_point = new_point
        return ans

[fockspaces]

since we only care about tail (head is in sorted order), we can maintain only cur_tail (int) instead of cur_point (list)

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort()
        cur_tail, ans = points[0][1], 1
        for i in range(1, len(points)):
            new_point = points[i]
            if cur_tail >= new_point[0]:
                cur_tail = min(cur_tail, new_point[1])
            else:
                ans += 1
                cur_tail = new_point[1]
        return ans

[fockspaces]

we can further init the dummpy point that will ensure overlapped with the first point, so that we can iterate through the first point (to make code more consistent)

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort()
        cur_tail, ans = points[0][1], 1
        for point in points:
            if cur_tail >= point[0]:
                cur_tail = min(cur_tail, point[1])
            else:
                ans += 1
                cur_tail = point[1]
        return ans