Python solution

  • 0

    Idea - sort the balloons, iterate in pairs determining if the following balloons fall within a 'boundary' of the previous arrow.

    class Solution(object):
        def findMinArrowShots(self, points):
            points = sorted(points)
            points.append([sys.maxint, sys.maxint])
            c, bound  = 0, None
            for p1, p2 in zip(points[:-1], points[1:]):
                if not bound:
                    c += 1
                    if p1[1] >= p2[0]:
                        bound = min(p2[1], p1[1])
                elif p2[0] <= bound:
                    bound = min(p2[1], bound)
                    bound = None
            return c

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.