题目描述
- 给定一些区间和一个数字 time，找到能覆盖
[0, time] 的最少区间数
示例
输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
输出：3
解释：选 [0,2], [8,10], [1,9]
输入：clips = [[0,1],[1,2]], time = 5
输出：-1
解释：找不到返回 -1
输入：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 开始，若区间包括标记点，更新右端点；若不包括，说明有点无法被覆盖
- 思路不难，但需要注意临界点
func videoStitching(clips [][]int, time int) int {sort.Slice(clips, func(i, j int) bool {return clips[i][0] < clips[j][0]})cnt, ed := 0, 0for i := 0; i < len(clips); {if ed < clips[i][0] { return -1 }r := edfor i < len(clips)&& clips[i][0] <= ed {r = max(r, clips[i][1])i ++}cnt, ed = cnt + 1, rif time <= ed { return cnt }}return -1
}
