Repository navigation
Expand file tree
/
Copy pathVideoStitching.cpp
More file actions
118 lines (102 loc) · 3.5 KB
/
Copy pathVideoStitching.cpp
File metadata and controls
118 lines (102 loc) · 3.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
// Source : https://leetcode.com/problems/video-stitching/
// Author : Hao Chen
// Date : 2019-10-01
/*****************************************************************************************************
*
* You are given a series of video clips from a sporting event that lasted T seconds. These video
* clips can be overlapping with each other and have varied lengths.
*
* Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends at time
* clips[i][1]. We can cut these clips into segments freely: for example, a clip [0, 7] can be cut
* into segments [0, 1] + [1, 3] + [3, 7].
*
* Return the minimum number of clips needed so that we can cut the clips into segments that cover the
* entire sporting event ([0, T]). If the task is impossible, return -1.
*
* Example 1:
*
* Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
* Output: 3
* Explanation:
* We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
* Then, we can reconstruct the sporting event as follows:
* We cut [1,9] into segments [1,2] + [2,8] + [8,9].
* Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].
*
* Example 2:
*
* Input: clips = [[0,1],[1,2]], T = 5
* Output: -1
* Explanation:
* We can't cover [0,5] with only [0,1] and [0,2].
*
* Example 3:
*
* Input: clips =
* [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]],
* T = 9
* Output: 3
* Explanation:
* We can take clips [0,4], [4,7], and [6,9].
*
* Example 4:
*
* Input: clips = [[0,4],[2,8]], T = 5
* Output: 2
* Explanation:
* Notice you can have extra video after the event ends.
*
* Note:
*
* 1 <= clips.length <= 100
* 0 <= clips[i][0], clips[i][1] <= 100
* 0 <= T <= 100
*
******************************************************************************************************/
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int T) {
//sort the clips
std::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 range
if (c[0] > T) continue;
// if clip is started from 0, then just simple initalize to 1
if (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 debug
void 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;
}
};