Leetcode 452. Minimum Number of

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

Minimum Number of Arrows to Burst Balloons

2. Solution

• Version 1

class Solution:
    def findMinArrowShots(self, points):
        if len(points) == 0:
            return 0
        points.sort(key=lambda p: p[0])
        total = 1
        overlap = points[0]
        for point in points:
            if overlap[1] < point[0]:
                total += 1
                overlap = point
            else:
                overlap[0] = point[0]
                overlap[1] = min(overlap[1], point[1])

        return total

• Version 2

class Solution:
    def findMinArrowShots(self, points):
        if len(points) == 0:
            return 0
        points.sort(key=lambda p: p[1])
        total = 1
        overlap = points[0]
        for point in points:
            if overlap[1] < point[0]:
                total += 1
                overlap = point

        return total

Reference

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