From 951d74f5469dafd161eed9a97edef25bd69283ac Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Fri, 7 Feb 2025 12:01:27 -0700 Subject: 1024. video stitching --- video_stitching.py | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 62 insertions(+) create mode 100644 video_stitching.py (limited to 'video_stitching.py') 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, + ) + ) -- cgit v1.2.3