Video Stitching Solutions in C++
Number 1024
Difficulty Medium
Acceptance 49.2%
Link LeetCode
Other languages —
Solutions
C++ solution by haoel/leetcode
// Source : https://leetcode.com/problems/video-stitching/// Author : Hao Chen// Date : 2019-10-01class Solution {public:int videoStitching(vector<vector<int>>& clips, int T) {//sort the clipsstd::sort(clips.begin(), clips.end(), [](vector<int>& x, vector<int>& y) {return x[0] < y[0] || (x[0] == y[0] && x[1] < y[1]);});//print(clips);// dynamic programming// dp[i] is the minmal clips from [o,i]vector<int> dp(T+1, -1);for (auto c : clips) {//edge case: out of the rangeif (c[0] > T) continue;// if clip is started from 0, then just simple initalize to 1if (c[0] == 0) {for (int i=c[0]; i<=min(T,c[1]); i++) dp[i] = 1;continue;}//if clip is not started from 0, seprate the range to two parts//the first part is the greater than 0, then second part is -1// 1) for the first part, need figure the minimal number// 2) for the second part, just simple add 1 with minimal number of first part.if (dp[c[0]] == -1 ) continue;int m = dp[c[0]];for (int i = c[0] + 1; i<= min(T, c[1]); i++) {if ( dp[i] > 0 ) m = min(m, dp[i]);else dp[i] = m + 1;}}//print(dp);return dp[T];}//used for debugvoid print(vector<vector<int>>& clips) {for (auto c : clips) {cout << "[" << c[0] <<","<< c[1] << "]"<< " ";}cout << endl;}void print(vector<int>& v) {for (auto i : v) {cout << i << ", ";}cout << endl;}};
C++ solution by liuyubobobo/Play-Leetcode
/// Source : https://leetcode.com/problems/video-stitching//// Author : liuyubobobo/// Time : 2019-04-06#include <iostream>#include <vector>using namespace std;/// Sorting and Greedy/// Time Complexity: O(nlogn)/// Space Complexity: O(1)class Solution {public:int videoStitching(vector<vector<int>>& clips, int T) {if(T == 0) return 0;sort(clips.begin(), clips.end(),[](const vector<int>& a, const vector<int>& b){if(a[0] != b[0]) return a[0] < b[0];return a[1] > b[1];});if(clips[0][0]) return -1;int res = 1, end = clips[0][1], tmax = end;if(end >= T) return 1;for(int i = 1; i < clips.size(); i ++)if(clips[i][0] <= end) tmax = max(tmax, clips[i][1]);else{res ++;end = tmax;if(end >= T) return res;if(clips[i][0] > end) return -1;}if(tmax >= T) return res + 1;return -1;}};int main() {vector<vector<int>> clips1 = {{0,2},{4,6},{8,10},{1,9},{1,5},{5,9}};cout << Solution().videoStitching(clips1, 10) << endl;// 3return 0;}