diff options
author | jack <0x6A73@pm.me> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <0x6A73@pm.me> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /min_num_arrow_balloon.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'min_num_arrow_balloon.py')
-rw-r--r-- | min_num_arrow_balloon.py | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/min_num_arrow_balloon.py b/min_num_arrow_balloon.py new file mode 100644 index 0000000..650cd00 --- /dev/null +++ b/min_num_arrow_balloon.py @@ -0,0 +1,31 @@ +# 452. Minimum Number of Arrows to Burst Balloons + +""" +there are some spherical balloons taped onto a flat wall that represents the +xy plane. the ballooons are represented as a 2d integer array 'points' where +'points[i] = [x_start, x_end]'. you do not know the exact y coordinates of +the balloons. arrows can be shot up directly vertically in the positive y +direction. from different points along the x axis. given the array points, +return the minimum number of arrows that must be shot to burst all balloons. +""" + + +class Solution(object): + def findMinArrowShots(self, points): + """ + :type points: List[List[int]] + :rtype: int + """ + points.sort(key=lambda p: p[1]) + ans, arrow = 0, 0 + for [start, end] in points: + if ans == 0 or start > arrow: + ans, arrow = ans + 1, end + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.findMinArrowShots(points=[[10, 16], [2, 8], [1, 6], [7, 12]])) + print(obj.findMinArrowShots(points=[[1, 2], [3, 4], [5, 6], [7, 8]])) + print(obj.findMinArrowShots(points=[[1, 2], [2, 3], [3, 4], [4, 5]])) |