add 1024

fishercoder1534 · fishercoder1534 · commit 6707b838ffd3 · 2021-07-14T15:17:01.000-07:00
diff --git a/README.md b/README.md
@@ -390,6 +390,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1030|[Matrix Cells in Distance Order](https://leetcode.com/problems/matrix-cells-in-distance-order/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1030.java) | |Easy|
 |1029|[Two City Scheduling](https://leetcode.com/problems/two-city-scheduling/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1029.java) | |Easy|
 |1025|[Divisor Game](https://leetcode.com/problems/divisor-game/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1025.java) | |Easy|Math, DP, Brainteaser, Game Theory|
+|1024|[Video Stitching](https://leetcode.com/problems/video-stitching/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1024.java) | |Medium|Array, DP, Greedy|
 |1022|[Sum of Root To Leaf Binary Numbers](https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1022.java) | |Easy|
 |1021|[Remove Outermost Parentheses](https://leetcode.com/problems/remove-outermost-parentheses/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1021.java) | |Easy|
 |1020|[Number of Enclaves](https://leetcode.com/problems/number-of-enclaves/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1020.java) | |Medium|Graph, DFS, BFS, recursion|
diff --git a/src/main/java/com/fishercoder/solutions/_1024.java b/src/main/java/com/fishercoder/solutions/_1024.java
@@ -0,0 +1,39 @@
+package com.fishercoder.solutions;
+
+import java.util.Arrays;
+
+public class _1024 {
+    public static class Solution1 {
+        /**
+         * Greedy
+         * Time: O(nlogn) where n is the number of clips
+         * Space: O(1)
+         */
+        public int videoStitching(int[][] clips, int time) {
+            Arrays.sort(clips, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
+            int count = 0;
+            int covered = 0;
+            for (int i = 0, start = 0; start < time; count++, start = covered) {
+                for (; i < clips.length && clips[i][0] <= start; i++) {
+                    covered = Math.max(covered, clips[i][1]);
+                }
+                if (start == covered) {
+                    return -1;
+                }
+            }
+            return count;
+        }
+    }
+
+    public static class Solution2 {
+        /**
+         * DP
+         * Time: ?
+         * Space: ?
+         */
+        public int videoStitching(int[][] clips, int time) {
+            //TODO: implement it.
+            return -1;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1024Test.java b/src/test/java/com/fishercoder/_1024Test.java
@@ -0,0 +1,33 @@
+package com.fishercoder;
+
+import com.fishercoder.common.utils.CommonUtils;
+import com.fishercoder.solutions._1024;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1024Test {
+    private static _1024.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1024.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(3, solution1.videoStitching(CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]"), 10));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals(-1, solution1.videoStitching(CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,1],[1,2]"), 5));
+    }
+
+    @Test
+    public void test3() {
+        assertEquals(-1, solution1.videoStitching(CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,2],[4,8]"), 5));
+    }
+
+}
