3830: 视频拼接

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：10 解决：3

题目描述

你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
使用一系列 clips 来表示这些片段，其中 clips[i] = [start_i, end_i] 表示第 i 个片段的开始时间和结束时间。我们可以对这些片段进行自由剪辑。
例如，片段 [0, 7] 可以被剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
我们需要将这些片段进行拼接，覆盖整个从 0 到 T 的时间段。请返回所需片段的最小数目。如果无法完成该任务，则返回 −1 。
注意：必须完整覆盖区间 [0,T] ，即拼接后的总时间段必须包含 0 时刻且结束时刻至少为 T 。

输入

第一行包含两个整数 n 和 T (1≤n≤100 , 1≤T≤100 )，分别表示视频片段的数量和需要覆盖的总时长。
接下来 n 行，每行包含两个整数 starti 和 endi (0≤starti<endi≤100 )，表示第 i 个视频片段的起始时间和结束时间。

输出

输出一个整数，表示覆盖 [0,T] 所需的最小片段数。如果无法完成，输出 −1 。

样例输入 复制 

6 10
0 2
4 6
8 10
1 9
1 5
5 9

样例输出 复制 

3

来源/分类

提交提交记录统计露一手!