aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--video_stitching.c78
-rw-r--r--video_stitching.py62
2 files changed, 140 insertions, 0 deletions
diff --git a/video_stitching.c b/video_stitching.c
new file mode 100644
index 0000000..1fd83db
--- /dev/null
+++ b/video_stitching.c
@@ -0,0 +1,78 @@
+// 1024. Video Stitching
+#include "leetcode.h"
+
+/*
+ * you are given a series of video clips from a sporting event that lasted
+ * 'time' seconds. these video clips can be overlapping with eachother and have
+ * varying lengths. each video clip is described by an array 'clips' where
+ * 'clips[i] = [start_i, end_i]' indicates that the i'th clip started at
+ * 'start_i' end 'end_i'. we can cut these clips into segments freely. return
+ * the minimum number of clips needed so that we can cut the clips needed so
+ * that we can cut the clips into segments that cover the entire sporting event
+ * '[0, time]'. if the task is impossible, return -1
+ */
+
+int cmp(const void *a, const void *b) {
+ int *aa = *(int **)a, *bb = *(int **)b;
+ if (aa[0] == bb[0])
+ return aa[1] - bb[1];
+ return aa[0] - bb[0];
+}
+
+int videoStitching(int **clips, int clipsSize, int *clipsColSize, int time) {
+ qsort(clips, clipsSize, sizeof(int *), cmp);
+ if (clips[0][0])
+ return -1;
+ int idx = -1;
+ for (int i = 0; i < clipsSize; i++) {
+ int left = clips[i][0], right = clips[i][1];
+ if (idx != -1 && clips[idx][1] >= time)
+ return idx + 1;
+ if (idx != -1 && left > clips[idx][1])
+ return -1;
+ if (idx == -1) {
+ idx++;
+ clips[idx][0] = clips[i][0];
+ clips[idx][1] = clips[i][1];
+ } else if (left == clips[idx][0] && right >= clips[idx][1]) {
+ clips[idx][1] = right;
+ continue;
+ } else if (left >= clips[idx][0] && right <= clips[idx][1]) {
+ continue;
+ } else if (left < clips[idx][0] && right > clips[idx][1]) {
+ while (idx != -1 && left < clips[idx][0] && right > clips[idx][1])
+ idx--;
+ left = fmax(clips[idx][1], clips[i][0]);
+ clips[++idx][0] = left;
+ clips[idx][1] = right;
+ } else if (left <= clips[idx][1] && right > clips[idx][1]) {
+ left = fmax(clips[idx][1], clips[i][0]);
+ clips[++idx][0] = left;
+ clips[idx][1] = right;
+ }
+ }
+ if (clips[idx][1] < time)
+ return -1;
+ return idx + 1;
+}
+
+int main() {
+ int c1i[6][2] = {{0, 2}, {4, 6}, {8, 10}, {1, 9}, {1, 5}, {5, 9}};
+ int c2i[2][2] = {{0, 1}, {1, 2}};
+ int c3i[16][2] = {{0, 1}, {6, 8}, {0, 2}, {5, 6}, {0, 4}, {0, 3},
+ {6, 7}, {1, 3}, {4, 7}, {1, 4}, {2, 5}, {2, 6},
+ {3, 4}, {4, 5}, {5, 7}, {6, 9}};
+ struct two_d_arr c1, c2, c3;
+ two_d_arr_init(&c1, ARRAY_SIZE(c1i), ARRAY_SIZE(c1i[0]), c1i);
+ two_d_arr_init(&c2, ARRAY_SIZE(c2i), ARRAY_SIZE(c2i[0]), c2i);
+ two_d_arr_init(&c3, ARRAY_SIZE(c3i), ARRAY_SIZE(c3i[0]), c3i);
+ printf("%d\n",
+ videoStitching(c1.arr, c1.row_size, c1.col_size, 3)); // expect: 3
+ printf("%d\n",
+ videoStitching(c2.arr, c2.row_size, c2.col_size, 5)); // expect: -1
+ printf("%d\n",
+ videoStitching(c3.arr, c3.row_size, c3.col_size, 9)); // expect: 3
+ two_d_arr_free(&c1);
+ two_d_arr_free(&c2);
+ two_d_arr_free(&c3);
+}
diff --git a/video_stitching.py b/video_stitching.py
new file mode 100644
index 0000000..7ada780
--- /dev/null
+++ b/video_stitching.py
@@ -0,0 +1,62 @@
+# 1024. Video Stitching
+
+"""
+you are given a series of video clips from a sporting event that lasted
+'time' seconds. these video clips can be overlapping with eachother and have
+varying lengths. each video clip is described by an array 'clips' where
+'clips[i] = [start_i, n_i]' indicates that the i'th clip started at
+'start_i' n 'n_i'. we can cut these clips into segments freely. return
+the minimum number of clips needed so that we can cut the clips needed so
+that we can cut the clips into segments that cover the entire sporting event
+'[0, time]'. if the task is impossible, return -1
+"""
+
+
+class Solution(object):
+ def videoStitching(self, clips, time):
+ """
+ :type clips: List[List[int]]
+ :type time: int
+ :rtype: int
+ """
+ n, m, ans = -1, 0, 0
+ for i, j in sorted(clips):
+ if m >= time or i > m:
+ break
+ elif n < i <= m:
+ ans, n = ans + 1, m
+ m = max(m, j)
+ return ans if m >= time else -1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.videoStitching(
+ clips=[[0, 2], [4, 6], [8, 10], [1, 9], [1, 5], [5, 9]], time=10
+ )
+ )
+ print(obj.videoStitching(clips=[[0, 1], [1, 2]], time=5))
+ print(
+ obj.videoStitching(
+ clips=[
+ [0, 1],
+ [6, 8],
+ [0, 2],
+ [5, 6],
+ [0, 4],
+ [0, 3],
+ [6, 7],
+ [1, 3],
+ [4, 7],
+ [1, 4],
+ [2, 5],
+ [2, 6],
+ [3, 4],
+ [4, 5],
+ [5, 7],
+ [6, 9],
+ ],
+ time=9,
+ )
+ )