Simple clustering O(n) solution


  • 0
    S
    class Solution(object):
        def findMinArrowShots(self, points):
            """
            :type points: List[List[int]]
            :rtype: int
            """
            if not points:return 0
            points = sorted(points, key= lambda (x,_): x)   # Sort by start so that in below loops xs >= minx
            minx, maxx = points[0][0], points[0][1]
            clusters = set([])
            for xs,xe in points[1:]:
                if xs > maxx:
                    clusters.add((minx, maxx))
                    minx, maxx = xs, xe
                    continue
                if xs <= maxx:
                    minx, maxx = xs, min(maxx,xe)
            clusters.add((minx, maxx))      # Add any missing clusters
            return len(clusters)            # Each cluster will need at least one arrow.
    

    For reasons beyond comprehension, this beats over 90% of the existing Python solutions. I am sure there are more concise ones out there but I hope this one is readable and does more than asked.


  • 0
    S

    Even if I replaced the second if block with an else which is what logically happens, it takes longer to run. Anyone care to explain why?


Log in to reply
 

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