题目描述
你将会获得一系列视频片段,这些片段来自于一项持续时长为 time
秒的体育赛事。这些片段可能有所重叠,也可能长度不一。
视频片段 clips[i]
都用区间进行表示:开始于 clips[i][0]
并于 clips[i][1]
结束。我们甚至可以对这些片段自由地再剪辑,例如片段 [0, 7]
可以剪切成 [0, 1] + [1, 3] + [3, 7]
三部分。
我们需要将这些片段进行再剪辑,并将剪辑后的内容拼接成覆盖整个运动过程的片段([0, time]
)。返回所需片段的最小数目,如果无法完成该任务,则返回 -1
。
样例
输入:clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
输出:3
解释:
选中 [0,2], [8,10], [1,9] 这三个片段。
然后,按下面的方案重制比赛片段:
将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9]。
现在手上的片段为 [0,2] + [2,8] + [8,10],而这些覆盖了整场比赛 [0, 10]。
输入:clips = [[0,1],[1,2]], time = 5
输出:-1
解释:
无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。
输入:
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]
],
time = 9
输出:3
解释:
选取片段 [0,4], [4,7] 和 [6,9] 。
限制
1 <= clips.length <= 100
0 <= starti <= endi <= 100
1 <= time <= 100
算法
(贪心) $O(n \log n)$
- 我们将所有区间按照左端点从小到大排序。此题就是找到最少个数的区间覆盖
[0, T]
。贪心的主要思想是,在左端点不超出当前右端点的范围内,找到下一个最大的右端点。 - 维护两个值和一个答案:
last_ed
表示能连续的最右端点;cur_ed
表示区间左端点在last_ed
前的右端点的最大值;ans
表示答案个数。 - 遍历时,如果当前区间左端点小于等于
last_ed
,则不断更新cur_ed
。 - 否则,如果左端点大于了
cur_ed
,则说明区间断开了,直接返回-1
。否则,更新last_ed
为cur_ed
,答案个数加 1。 - 如果在遍历过程中,出现了
cur_ed >= T
,则返回答案个数加 1。
时间复杂度
- 排序后扫一遍,故时间复杂度为 $O(n \log n)$。
空间复杂度
- 只需要常数的额外空间。
C++ 代码
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int time) {
int n = clips.size();
sort(clips.begin(), clips.end());
int last_ed = 0, ans = 0;
int cur_ed = 0;
for (const auto &v: clips) {
int st = v[0], ed = v[1];
if (st <= last_ed) {
cur_ed = max(cur_ed, ed);
} else {
if (st > cur_ed)
return -1;
last_ed = cur_ed;
cur_ed = max(cur_ed, ed);
ans++;
}
if (cur_ed >= time)
return ans + 1;
}
return -1;
}
};