diff options
Diffstat (limited to 'video_stitching.py')
-rw-r--r-- | video_stitching.py | 62 |
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, + ) + ) |