6346: [2020CSP普及 完善程序2]:最小区间覆盖

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:2 通过:2

题目描述

给出 n 个区间,第 i 个区间的左右端点是 [ai,bi]。现在要在这些区间中选出若干个,使得区间 [0, m] 被所选区间的并覆盖(即每一个 0≤i≤m 都在某个所选的区间中)。保证答案存在,求所选区间个数的最小值。

最小区间覆盖)给出 n 个区间,第 i 个区间的左右端点是 [ai,bi]。现在要在这些区间中选出若干个,使得区间 [0,m] 被所选区间的并覆盖(即每一个 0≤i≤m 都在某个所选的区间中)。保证答案存在,求所选区间个数的最小值。
输入第一行包含两个整数 n 和 m (1≤n≤5000,1≤m≤109
接下来 n 行,每行两个整数 ai,bi (0≤ai,bi≤m)。
提示:使用贪心法解决这个问题。先用 O(n2) 的时间复杂度排序,然后贪心选择这些区间。




输入格式

输入第一行包含两个整数 n 和 m (1≤n≤5000,1≤m≤109) 

接下来 n 行,每行两个整数 ai,bi (0≤ai,bi≤m)

输出格式

所选区间个数的最小值。

输入样例 复制

3 10
0 8
5 10
0 10

输出样例 复制

1