My Python Solution from pool & slow to much more speedy

• 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

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