Video Stitching: Finding Minimum Clips to Cover Time Range
Video Stitching: Finding Minimum Clips to Cover Time Range
Given start and end times of clips, find the minimum number of clips that can stitch together to cover 0 to T minutes.
Dynamic Programming Approach
Each segment from 0 to T has a count of choices. We consider how each given clip relates to every segment. This breaks down into five cases.
// time: O(N³)
// space: O(N²)
int videoStitching(vector<vector<int>>& clips, int T) {
int kInf=101;
vector<vector<int> > dp(T+1, vector<int>(T+1, kInf));
for(auto clip : clips) {
int s=clip[0];
int e=clip[1];
for(int l=1;l<=T;++l) {
for(int i=0;i<=T-l;++i) {
int j=i+l;
if (s > j || e < i) continue;
if (s<=i && e>=j) dp[i][j]=1;
else if (s <= i) dp[i][j]=min(dp[i][j], dp[e][j]+1);
else if (e >= j) dp[i][j]=min(dp[i][j], dp[i][s]+1);
else dp[i][j]=min(dp[i][j], dp[i][s]+dp[e][j]+1);
}
}
}
return dp[0][T] == kInf ? -1 : dp[0][T];
}Greedy Approach
Sort directly, then take the farthest endpoint that satisfies the current starting point at each step.
// time: O(NlogN)
// space: O(1)
int videoStitching(vector<vector<int>>& clips, int T) {
sort(clips.begin(), clips.end());
int res=0;
for(int i=0,st=0,end=0;st<T;st=end, ++res) {
while(i<clips.size() && clips[i][0]<=st)
end=max(end, clips[i++][1]);
if (end==st) return -1;
}
return res;
}#DP #greedy