leetcode-greedy

452. Minimum Number of Arrows to Burst Balloons.py

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        n = len(points)
        # edge case
        if n == 0:
            return 0
        ending_time, ans = float('-inf'), 0 # the earliest end time
        # sort the balloons by their end x-coordinate
        for i in sorted(points, key=lambda x: x[1]):
            start_time = i[0]
            if start_time > ending_time: 
                # since xstart ≤ x ≤ xend, here we take equal as overlapping
                ending_time = i[1]
            else: 
                ans += 1 # number of ballons we need to remove make rest of them non-overlapping
        return n - ans