//使用java dfs
public int videoStitching(int[][] clips, int T) {
//bfs
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
for (int i = 0;i < clips.length; i ++)
if (clips[i][0] == 0){
queue.offer(clips[i][1]);
queue.offer(1);
visited.add(clips[i][0]* 1000 + clips[i][1]);
}
if (queue.isEmpty())
return -1;
int end = -1, step = -1;
while ( !queue.isEmpty() ){
end = queue.poll();
step = queue.poll();
if (end >= T)
return step;
for (int i = 0; i< clips.length; i++){
if (!visited.contains(clips[i][0]* 1000 + clips[i][1]))
if (end >= clips[i][0]){
queue.offer(clips[i][1]);
queue.offer(step + 1);
visited.add(clips[i][0]* 1000 + clips[i][1]);
}
}
}
return -1;
}
python dp
def videoStitching(self, clips: List[List[int]], T: int) -> int:
#dp[i] 代表 到i结尾时间的最小个数
clips.sort()
n = len(clips)
dp = [float('inf')]* n
if clips[0][0] != 0:
return -1
for i in range(n):
if clips[i][0] == 0:
dp[i] = 1
else:
break
for i in range(n):
for j in range(i):
if dp[j] != float('inf') and clips[j][1] >= clips[i][0] :
dp[i] = min(dp[i], dp[j] + 1)
res = float('inf')
for i in range(n):
if clips[i][1] >= T:
res = min(res, dp[i])
return res if res != float('inf') else - 1