aboutsummaryrefslogtreecommitdiff
path: root/min_num_arrow_balloon.rs
diff options
context:
space:
mode:
Diffstat (limited to 'min_num_arrow_balloon.rs')
-rw-r--r--min_num_arrow_balloon.rs20
1 files changed, 20 insertions, 0 deletions
diff --git a/min_num_arrow_balloon.rs b/min_num_arrow_balloon.rs
new file mode 100644
index 0000000..6204bfe
--- /dev/null
+++ b/min_num_arrow_balloon.rs
@@ -0,0 +1,20 @@
+struct Solution;
+
+impl Solution {
+ pub fn find_min_arrow_shots(mut points: Vec<Vec<i32>>) -> i32 {
+ points.sort_unstable_by(|a, b| a[1].cmp(&b[1]));
+ let (mut arrows, mut target) = (0, points[0][1]);
+ for p in points {
+ if p[0] > target && p[1] > target {
+ arrows += 1;
+ target = p[1];
+ }
+ }
+ arrows + 1
+ }
+}
+
+fn main() {
+ let points = vec![vec![10,16],vec![2,8],vec![1,6],vec![7,12]];
+ println!("{}", Solution::find_min_arrow_shots(points)); //expect: 2
+}