aboutsummaryrefslogtreecommitdiff
path: root/video_stitching.py
blob: 7ada780f81fafa7ebbaf1b908fda730e98dcffad (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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,
        )
    )