第41题 （最小区间覆盖）给出 n 个区间，第 i 个区间的左右端点是[ai,bi]。现在要在这些区间中选出若干个，使得区间 [0,m][0,m] 被所选区间的并覆盖（即每一个 0≤i≤m 都在某个

第41题EPO100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

（最小区间覆盖）给出 n 个区间，第 i 个区间的左右端点是[ai,bi]。现在要在这些区间中选出若干个，使得区间 [0,m][0,m] 被所选区间的并覆盖（即每一个 0≤i≤m 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。EPO100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入第一行包含两个整数 n 和 m（1≤n≤5000, 1≤m≤109）。EPO100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

接下来 n 行，每行两个证书 ai，bi（0≤ai，bi≤m）。EPO100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

提示：使用贪心法解决这个问题。先用 Θ(n^2) 的时间复杂度排序，然后贪心选择这些区间。EPO100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

试补全程序。EPO100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
 EPO100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1. #include <cstdio> 
2. using namespace std; 
3.   
4. int n, i; 
5.   
6. int main() { 
7.     scanf("%d", &n); 
8.     for (i = ①; ② <= n; i ++) { 
9.         ③ { 
10.             printf("%d ", i); 
11.             n = n / i; 
12.         } 
13.     } 
14.     if (④) { 
15.         printf("%d ", ⑤); 
16.     } 
17.     return 0; 
18. } 

③ 处应填（ ）EPO100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

A[i].b > A[p - 1].b

A[i].b < A[i - 1].b

A[i].b > A[i - 1].b

A[i].b < A[p - 1].b