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

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

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

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

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

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

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

1. #include <iostream> 
2.   
3. using namespace std; 
4.   
5. const int MAXN = 5000; 
6. int n, m; 
7. struct segment { int a, b; } A[MAXN]; 
8.   
9. void sort() // 排序 
10. { 
11.     for (int i = 0; i < n; i++) 
12.         for (int j = 1; j < n; j++) 
13.             if (①) 
14.             { 
15.                 segment t = A[j]; 
16.                 ② 
17.             } 
18. } 
19.   
20. int main() 
21. { 
22.     cin >> n >> m; 
23.     for (int i = 0; i < n; i++) 
24.         cin >> A[i].a >> A[i].b; 
25.     sort(); 
26.     int p = 1; 
27.     for (int i = 1; i < n; i++) 
28.         if (③) 
29.             A[p++] = A[i]; 
30.     n = p; 
31.     int ans = 0, r = 0; 
32.     int q = 0; 
33.     while (r < m) 
34.     { 
35.         while (④) 
36.             q++; 
37.         ⑤; 
38.         ans++; 
39.     } 
40.     cout << ans << endl; 
41.     return 0; 
42. } 

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

q + 1 < n && A[q + 1].a <= r

q + 1 < n && A[q + 1].b <= r

q < n && A[q].a <= r

q < n && A[q].b <= r