add 452

fishercoder1534 · fishercoder1534 · commit c5bf94e2edaa · 2017-05-11T22:50:11.000-07:00
diff --git a/README.md b/README.md
@@ -93,6 +93,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |455|[Assign Cookies](https://leetcode.com/problems/assign-cookies/)|[Solution](../master/src/main/java/com/stevesun/solutions/AssignCookies.java)| O(n)|O(1) | Easy|
 |454|[4Sum II](https://leetcode.com/problems/4sum-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/_454.java) | O(n) |O(n) | Medium| HashMap
 |453|[Minimum Moves to Equal Array Elements](https://leetcode.com/problems/minimum-moves-to-equal-array-elements/)|[Solution](../master/src/main/java/com/stevesun/solutions/MinimumMovestoEqualArrayElements.java)| O(n)|O(1) | Easy|
+|452|[Minimum Number of Arrows to Burst Balloons](https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/)|[Solution](../master/src/main/java/com/stevesun/solutions/_452.java) | O(nlogn) |O(1) | Medium| Array, Greedy
 |451|[Sort Characters By Frequency](https://leetcode.com/problems/sort-characters-by-frequency/)|[Solution](../master/src/main/java/com/stevesun/solutions/SortCharactersByFrequency.java) | O(nlogn) |O(n) | Medium| HashMap
 |449|[Serialize and Deserialize BST](https://leetcode.com/problems/serialize-and-deserialize-bst/)|[Solution](../master/src/main/java/com/stevesun/solutions/SerializeandDeserializeBST.java)| O(n)|O(h) | Medium| BFS
 |448|[Find All Numbers Disappeared in an Array](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/)|[Solution](../master/src/main/java/com/stevesun/solutions/FindAllNumbersDisappearedinanArray.java)| O(n)|O(1) | Easy| Array, HashMap
diff --git a/src/main/java/com/stevesun/solutions/_452.java b/src/main/java/com/stevesun/solutions/_452.java
@@ -1,5 +1,7 @@
 package com.stevesun.solutions;
 
+import java.util.Arrays;
+
 /**
  *452. Minimum Number of Arrows to Burst Balloons
  *
@@ -27,8 +29,24 @@
  */
 public class _452 {
 
+    //credit: https://discuss.leetcode.com/topic/66579/java-greedy-soution/6
     public int findMinArrowShots(int[][] points) {
-        return 0;
+
+        if(points==null || points.length==0) return 0;
+        // sort points based on their end point.
+        Arrays.sort(points, (p1, p2) -> Integer.compare(p1[1],p2[1]));
+        int currentEnd = points[0][1];
+        int count = 1;
+        for(int[] p: points)
+        {
+            // if the point starts after currentEnd, it means this balloons not been bursted. Then we shot the balloon in its end point. Otherwise, means this balloon has been bursted, then ignore it.
+            if(p[0]>currentEnd) {
+                count++;
+                currentEnd = p[1];
+            }
+            else continue;
+        }
+        return count;
     }
 
 }
