My Python Solution from pool & slow to much more speedy


  • 0

    First of all, think of the balloons as intervals and sort them based the begin timestamp.

    Then think greedy: that is alway pick the end point as a shot if there should be. if the begin of the new come interval is greater than the existing interval min end timestamp, this indicates a shot should be used.

    Based on this piece of idea, this straight forward solution came out:

    class Solution(object):
        def findMinArrowShots(self, points):
            points.sort(key = lambda x: x[0])
            heap, ans = [], 0
            for point in points:
                if heap and heap[0] < point[0]:
                    ans += 1
                    heap = []
                heapq.heappush(heap, point[1])
            ans = ans + 1 if heap else ans
            return ans
    

    However, it seems way too slow. Even by using the same idea, I decided to avoid the use of heap since the only value can be stored as a variable(Min I called it):

    class Solution(object):
        def findMinArrowShots(self, points):      
            points.sort(key = lambda x: x[0])
            ans, Min = 0, -0xffffffff
            for point in points:
                if point[0] > Min:
                    ans += 1
                    Min = point[1]
                else:
                    Min = min(Min, point[1])
            return ans
    

Log in to reply
 

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