3843: 最小区间覆盖(2020完善程序2)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：3
题目描述
2.(最小区间覆盖)给出n个区间，第i个区间的左右端点是[ai,bi]。现在 要在这些区间中选出若干个，使得区间[0,m]被所选区间的并覆盖(即每 一个0≤i≤m都在某个所选的区间中)。保证答案存在，求所选区间个数 的最小值。
输入第一行包含两个整数n和m(1≤n≤5000,1≤m≤10^9)。 接下来n行，每行两个整数ai,bi(O≤ai,b₁≤m)。
提示：使用贪心法解决这个问题。先用θ(n²)的时间复杂度排序，然后贪心 选择这些区间。
试补全程序。
输入第一行包含两个整数n和m(1≤n≤5000,1≤m≤10^9)。 接下来n行，每行两个整数ai,bi(O≤ai,b₁≤m)。
提示：使用贪心法解决这个问题。先用θ(n²)的时间复杂度排序，然后贪心 选择这些区间。
试补全程序。
输入
输入第一行包含两个整数n和m(1≤n≤5000,1≤m≤10^9)。
接下来n行，每行两个整数ai,bi(O≤ai,b₁≤m)。
输出
求所选区间个数 的最小值。
样例输入 复制
8 10
0 3
1 2
2 3
2 5
3 6
4 7
6 8
7 10样例输出 复制
4提示
