add a solution for 452

fishercoder1534 · fishercoder1534 · commit 60a560806a27 · 2021-10-13T12:52:00.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_452.java b/src/main/java/com/fishercoder/solutions/_452.java
@@ -17,7 +17,8 @@ public int findMinArrowShots(int[][] points) {
             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 the point starts after currentEnd, it means this balloons not been burst.
+                // Then we shot the balloon in its end point. Otherwise, means this balloon has been burst, then ignore it.
                 if (p[0] > currentEnd) {
                     count++;
                     currentEnd = p[1];
@@ -28,4 +29,29 @@ public int findMinArrowShots(int[][] points) {
             return count;
         }
     }
+
+    public static class Solution2 {
+        /**
+         * I'm glad to have come up with this solution on my own on 10/13/2021:
+         * we'll have to sort the balloons by its ending points, a counter case to this is below:
+         * {{0, 6}, {0, 9}, {7, 8}}
+         * if we sort by starting points, then it becomes: {0, 6}, {0, 9}, {7, 8}, this way, if we shoot 9, {0, 6} won't be burst
+         * however, if we sort by ending points, then it becomes: {0, 6}, {7, 8}, {0, 9},
+         * then we shoot at 6, then at 8, this gives us the result of bursting all balloons.
+         */
+        public int findMinArrowShots(int[][] points) {
+            Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
+            int minArrows = 1;
+            long end = points[0][1];
+            for (int i = 1; i < points.length; i++) {
+                if (points[i][0] <= end) {
+                    continue;
+                } else {
+                    minArrows++;
+                    end = points[i][1];
+                }
+            }
+            return minArrows;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_452Test.java b/src/test/java/com/fishercoder/_452Test.java
@@ -0,0 +1,44 @@
+package com.fishercoder;
+
+import com.fishercoder.common.utils.CommonUtils;
+import com.fishercoder.solutions._452;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _452Test {
+    private static _452.Solution1 solution1;
+    private static _452.Solution2 solution2;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _452.Solution1();
+        solution2 = new _452.Solution2();
+    }
+
+    @Test
+    public void test1() {
+        int[][] points = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray
+                ("[3,9],[7,12],[3,8],[6,8],[9,10],[2,9],[0,9],[3,9],[0,6],[2,8]");
+        assertEquals(2, solution1.findMinArrowShots(points));
+        assertEquals(2, solution2.findMinArrowShots(points));
+    }
+
+    @Test
+    public void test2() {
+        int[][] points = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray
+                ("[-2147483646,-2147483645],[2147483646,2147483647]");
+        assertEquals(2, solution1.findMinArrowShots(points));
+        assertEquals(2, solution2.findMinArrowShots(points));
+    }
+
+    @Test
+    public void test3() {
+        int[][] points = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray
+                ("[0,6],[0,9],[7,8]");
+        assertEquals(2, solution1.findMinArrowShots(points));
+        assertEquals(2, solution2.findMinArrowShots(points));
+    }
+
+}
