452. Minimum Number of Arrows to Burst Balloons

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

solution

• 关键，重叠一个后更新右边界用于判断下一个

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

时间复杂度：O() 空间复杂度：O()

• interval题目template可以采用以下方式：记录额外一个结果表

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: x[1])

        res_list = [points[0]]
        for i in range(1, len(points)):
            if points[i][0] <= res_list[-1][1]:
                l = max(points[i][0], res_list[-1][0])
                r = min(points[i][1], res_list[-1][1])
                res_list.pop()
                res_list.append([l, r])
            else:
                res_list.append(points[i])
        return len(res_list)