题目大意：
视频拼接
你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1024
解题思路分析：
这道题我使用的贪心算法，所谓贪心，就是每次尽可能的找到当前最好的结果。比如我们当前的片段为[0, 5]，那么下一片段在保证与当前有交集的前提下，尽量覆盖到更远的范围。比如，[4, 6]和[1, 10]，显然后者是更好的结果。具体思路为：
- 首先先遍历出，以所有起点开始，能够覆盖到的最大距离，比如有[0, 5]和[0, 10]，那么[0, 10]是最优解，就是说从0开始能够覆盖的最大距离为10。
- 当得知每个点能够覆盖的最大距离之后，从0这个起点开始循环，先看0能够覆盖到的最远距离，我们称之为currendEnd。然后在1到currendEnd范围内查看他们能覆盖到的最远距离nextMaxEnd是多少，如果nextMaxEnd小于等于currendEnd，说明0到其能覆盖范围内的所有起点都无法跨越0至currendEnd的距离，也就无法将后面的片段连接起来，直接返回false。反之，如果nextMaxEnd大于currendEnd，说明我们已经可以覆盖到更远的nextMaxEnd范围内，这时我们再从currendEnd与nextMaxEnd之间寻找后面更远的覆盖范围，直到nextMaxEnd大于等于目标T为止。总共寻找的次数就是最终结果。
看下实现代码：
public int videoStitching(int[][] clips, int T) {
int[] rangeMap = new int[T + 1]; // 用于存储每个起点能覆盖到的最大范围
for (int[] clip : clips) {
if (clip[0] > T) {
continue;
}
rangeMap[clip[0]] = Math.max(rangeMap[clip[0]], clip[1]);
}
// 从0开始，看其最远覆盖范围是多少。
int currendEnd = rangeMap[0];
// 返回结果，将0计入次数中，所以初始值为1
int res = 1;
// 因为0已经预先定义好，所以从1开始循环
int i = 1;
// 当currendEnd 大于等于目标值T时，结束循环
while (currendEnd < T) {
// 定义下一个最远覆盖范围
int nextMaxEnd = 0;
// 从当前位置到currendEnd范围内的所有数为起点，找其能覆盖的最远距离
for (int j = i; j <= currendEnd; j++) {
nextMaxEnd = Math.max(nextMaxEnd, rangeMap[j]);
}
// 如果找到的最远距离无法超越currendEnd，说明后续片段无法连接
if (nextMaxEnd <= currendEnd) {
return -1;
}
// 将i至于currendEnd之后
i = currendEnd + 1;
// 当前能覆盖的最远距离更新为nextMaxEnd
currendEnd = nextMaxEnd;
// 次数加一
res++;
}
return res;
} 本解法用时0ms。
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1024-video-stitching-解题思路分析/