aboutsummaryrefslogtreecommitdiff
path: root/min_num_arrow_balloon.py
diff options
context:
space:
mode:
authorjack <0x6A73@pm.me>2024-06-14 13:13:15 -0600
committerjack <0x6A73@pm.me>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /min_num_arrow_balloon.py
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'min_num_arrow_balloon.py')
-rw-r--r--min_num_arrow_balloon.py31
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]]))