aboutsummaryrefslogtreecommitdiff
path: root/video_stitching.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-02-07 12:01:27 -0700
committerJack Sangdahl <[email protected]>2025-02-07 12:02:15 -0700
commit951d74f5469dafd161eed9a97edef25bd69283ac (patch)
tree7fa3598587c7951028186198aa60022bcbc8eccf /video_stitching.py
parent4a2a2c3a4c210d5f14c668df196ecba0bd3694a6 (diff)
downloadleetcode-951d74f5469dafd161eed9a97edef25bd69283ac.tar.gz
leetcode-951d74f5469dafd161eed9a97edef25bd69283ac.zip
1024. video stitching
Diffstat (limited to 'video_stitching.py')
-rw-r--r--video_stitching.py62
1 files changed, 62 insertions, 0 deletions
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,
+ )
+ )