Approach 1: Greedy (1)
The idea is to get the farthest ending position for each starting position. Initially, the starting position is 0. So the max ending position will be all such segments where clips[i][0] is 0. Suppose this farthest ending position becomes farthest. Now, in the step, we can choose any segment whose starting point, clips[i][0], is less that farthest. Out of all these segments, we would again like to choose the segment which has maximum ending value.
Sort the clips by the starting point. Since clips are sorted, we need to only analyze each clip once. For each round, we check all overlapping clips (clips[i][0] <= st) and advance our stitching position as far as we can (end = max(end, clips[i][1])).
Return -1 if we cannot advance our stitching position (st == end).
int videoStitching(vector<vector<int>>& clips, int T) {
int res = 0, st=0, end=0;
sort(begin(clips), end(clips));
for (auto i = 0; st < T; st = end, res++) {
while (i < clips.size() && clips[i][0] <= st) {
end = max(end, clips[i][1]);
i++;
}
if (st == end) return -1;
}
return res;
}
Time complexity: O(nlogn)
Approach 2: Greedy (2)
This problem can be solved using the idea of LC 45. Jump Game II. I recommend reading the solution of Jump Game II as the below code adopts the same idea.
Think of each interval [beg, end] as a jump from array[beg] to array[end]. For each index, we only need to store the maximum such ending value.
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int T) {
if (clips.size()==0)
return -1;
vector<int> jumps(T, 0);
for (auto c : clips)
if (c[0]<T)
jumps[c[0]] = max(jumps[c[0]], c[1]);
int ans = 0, i, farthest, end;
for (i=0, farthest=0, end=0; i<jumps.size(); i++) {
if (end<i)
return -1;
farthest = max(farthest, jumps[i]);
if (end==i) {
end = farthest;
ans++;
}
}
return end>=T ? ans : -1;
}
};
Time complexity: O(n)
Approach 3: Dynamic Programming
Define dp[i] as maximum ending point which can be reached using the first i clips. The below code is self-explanatory:
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int T) {
int n = clips.size();
vector<int> dp(n+1);
dp[0] = 0;
for (int i=1; i<=n; i++) {
dp[i] = dp[i-1];
for (int j=0; j<n; j++) {
if (clips[j][0]<=dp[i-1]) { // if we can reach the current clip
dp[i] = max(dp[i], clips[j][1]);
}
}
if (dp[i]>=T)
return i;
}
return -1;
}
};
Time complexity: O(N*N)