1024. Video Stitching

//使用java dfs

1    public int videoStitching(int[][] clips, int T) {
2        //bfs
3        Queue<Integer> queue = new LinkedList<>();
4        Set<Integer> visited = new HashSet<>();
5        for (int i = 0;i < clips.length; i ++)
6            if (clips[i][0] == 0){
7                queue.offer(clips[i][1]);
8                queue.offer(1);
9                visited.add(clips[i][0]* 1000 + clips[i][1]);
10            }
11        if (queue.isEmpty())
12            return -1;
13        
14        int end = -1, step = -1;
15        while ( !queue.isEmpty() ){
16            end = queue.poll();
17            step = queue.poll();
18            if (end >= T)
19                return step;
20            for (int i = 0; i< clips.length; i++){
21                if (!visited.contains(clips[i][0]* 1000 + clips[i][1]))
22                    if (end >= clips[i][0]){
23                        queue.offer(clips[i][1]);
24                        queue.offer(step + 1);
25                        visited.add(clips[i][0]* 1000 + clips[i][1]);
26                    }
27            }
28        }
29        return -1;
30    }

python dp

1def videoStitching(self, clips: List[List[int]], T: int) -> int:
2        #dp[i] 代表 到i结尾时间的最小个数
3        clips.sort()
4        n = len(clips)
5        dp = [float('inf')]* n
6        if clips[0][0] != 0:
7            return -1
8        for i in range(n):
9            if clips[i][0] == 0:
10                dp[i] = 1
11            else:
12                break
13        for i in range(n):
14            for j in range(i):
15                if dp[j] != float('inf') and clips[j][1] >= clips[i][0] :
16                    dp[i] = min(dp[i], dp[j] + 1)
17        res = float('inf')
18        for i in range(n):
19            if clips[i][1] >= T:
20                res = min(res, dp[i])
21        return res if res != float('inf') else - 1