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

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

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

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

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

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

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

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

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

A[j + 1] = A[j]; A[j] = t;

A[j - 1] = A[j]; A[j] = t;

A[j] = A[j + 1]; A[j + 1] = t;

A[j] = A[j - 1]; A[j - 1] = t;