add a solution for 452

fishercoder1534 · fishercoder1534 · commit 82a298e96e67 · 2021-11-04T14:48:32.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_452.java b/src/main/java/com/fishercoder/solutions/_452.java
@@ -54,4 +54,31 @@ public int findMinArrowShots(int[][] points) {
             return minArrows;
         }
     }
+
+    public static class Solution3 {
+        /**
+         * Another approach of mine: completely original.
+         * 1. Sort the points by start first, if tie, sort by end, both ascendingly.
+         * 2. While checking, we'll keep updating the ending to be the smaller one so that we don't possibly miss to burst a balloon. See test case 4 for this class.
+         */
+
+        public int findMinArrowShots(int[][] points) {
+            int arrowShots = 0;
+            Arrays.sort(points, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
+            for (int i = 0; i < points.length; ) {
+                int end = points[i][1];
+                int j = i + 1;
+                for (; j < points.length; j++) {
+                    if (points[j][0] <= end) {
+                        end = Math.min(end, points[j][1]);
+                    } else {
+                        break;
+                    }
+                }
+                i = j;
+                arrowShots++;
+            }
+            return arrowShots;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_452Test.java b/src/test/java/com/fishercoder/_452Test.java
@@ -10,11 +10,13 @@
 public class _452Test {
     private static _452.Solution1 solution1;
     private static _452.Solution2 solution2;
+    private static _452.Solution3 solution3;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _452.Solution1();
         solution2 = new _452.Solution2();
+        solution3 = new _452.Solution3();
     }
 
     @Test
@@ -23,6 +25,7 @@ public void test1() {
                 ("[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));
+        assertEquals(2, solution3.findMinArrowShots(points));
     }
 
     @Test
@@ -31,6 +34,7 @@ public void test2() {
                 ("[-2147483646,-2147483645],[2147483646,2147483647]");
         assertEquals(2, solution1.findMinArrowShots(points));
         assertEquals(2, solution2.findMinArrowShots(points));
+        assertEquals(2, solution3.findMinArrowShots(points));
     }
 
     @Test
@@ -39,6 +43,16 @@ public void test3() {
                 ("[0,6],[0,9],[7,8]");
         assertEquals(2, solution1.findMinArrowShots(points));
         assertEquals(2, solution2.findMinArrowShots(points));
+        assertEquals(2, solution3.findMinArrowShots(points));
+    }
+
+    @Test
+    public void test4() {
+        int[][] points = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray
+                ("[9,12],[1,10],[4,11],[8,12],[3,9],[6,9],[6,7]");
+        assertEquals(2, solution1.findMinArrowShots(points));
+        assertEquals(2, solution2.findMinArrowShots(points));
+        assertEquals(2, solution3.findMinArrowShots(points));
     }
 
 }
