add a solution for 435

fishercoder1534 · fishercoder1534 · commit 45d9170b80c0 · 2021-10-13T11:11:58.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_435.java b/src/main/java/com/fishercoder/solutions/_435.java
@@ -27,4 +27,24 @@ public int eraseOverlapIntervals(int[][] intervals) {
         }
     }
 
+    public static class Solution2 {
+        /**
+         * This is sorting my starting time, the key here is that we'll want to update end time when an erasure is needed:
+         * we use the smaller end time instead of the bigger one which is more likely to overlap with others.
+         */
+        public int eraseOverlapIntervals(int[][] intervals) {
+            Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
+            int erasures = 0;
+            int end = intervals[0][1];
+            for (int i = 1; i < intervals.length; i++) {
+                if (intervals[i][0] < end) {
+                    erasures++;
+                    end = Math.min(end, intervals[i][1]);
+                } else {
+                    end = intervals[i][1];
+                }
+            }
+            return erasures;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_435Test.java b/src/test/java/com/fishercoder/_435Test.java
@@ -9,16 +9,26 @@
 
 public class _435Test {
     private static _435.Solution1 solution1;
+    private static _435.Solution2 solution2;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _435.Solution1();
+        solution2 = new _435.Solution2();
     }
 
     @Test
     public void test1() {
         int[][] intervals = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[1,2],[2,3],[3,4],[1,3]");
         assertEquals(1, solution1.eraseOverlapIntervals(intervals));
+        assertEquals(1, solution2.eraseOverlapIntervals(intervals));
+    }
+
+    @Test
+    public void test2() {
+        int[][] intervals = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[-52,31],[-73,-26],[82,97],[-65,-11],[-62,-49],[95,99],[58,95],[-31,49],[66,98],[-63,2],[30,47],[-40,-26]");
+        assertEquals(7, solution1.eraseOverlapIntervals(intervals));
+        assertEquals(7, solution2.eraseOverlapIntervals(intervals));
     }
 
 }
