题目描述：
你将会获得一系列视频片段，这些片段来自于一项持续时长为 time 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
使用数组 clips 描述所有的视频片段，其中 clips[i] = [starti, endi] 表示：某个视频片段开始于 starti 并于 endi 结束。
甚至可以对这些片段自由地再剪辑：
- 例如，片段
[0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, time]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。
数据范围：
$1\le clips.len \le 100; 1\le time \le 100$ 。
题解：
首先排序，起点相同时，终点越大越好，否则就是起点越小越好。
然后假设上一个区间是 $[0,0]$ ，每次选择一个区间起点在这里面，并且终点最远的。也就是起点需要小于等于 $preEnd$ ，找到最远的 $nextEnd$ 。然后加到答案里面，将 $preEnd$ 换成 $nextEnd$ 。
代码：
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int videoStitching(vector<vector<int>> &clips, int time)
{
sort(clips.begin(), clips.end(), [](const vector<int> &x, const vector<int> &y)
{ return x[0] == y[0] ? x[1] > y[1] : x[0] < y[0]; });
int i = 0, j;
int n = clips.size();
if (clips[0][0] != 0)
return -1;
int ans = 0;
int start, end = 0;
int next_end;
while (i < n)
{
if(end >= time) return ans;
if (clips[i][0] > end)
return -1;
next_end = 0;
while (i < n && clips[i][0] <= end)
{
next_end = max(next_end, clips[i][1]);
++i;
}
ans++;
end = next_end;
}
if (end < time)
return -1;
return ans;
}
};
|