Leetcode 452. Minimum Number of Arrows to Burst Balloons

2021/02/02 07:16
阅读数 25

文章作者: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/
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部