完善程序（2） 6-10题 组合题 （最小区间覆盖）给出n个区间，第i个区间的左右端点是［ai, bi］。现在 要在这些区间中选出若干个，使得区间［0,m］被所选区间的并覆盖（即每 一个0≤i≤m都在某个所选的区间中）。保证答案存在，求所选区间个数 的最小值。 输入第一行包含两个整数n和m（1≤n≤5000, 1≤m≤10^9 ） 接下来n行,每行两个整数ai，bi（0≤ai, bi ≤ m）。 提示：使用贪心法解决这个问题。先用0(n^2)的时间复杂度排序，然后贪心 选择这些区间。 试补全程序。 #include using namespace std; const int MAXN = 5000; int n, m; struct segment { int a, b; } A[MAXN]; void sort() // 排序 { for (int i = 0; i > n >> m; for (int i = 0; i > A[i].a >> A[i].b; sort(); int p = 1; for (int i = 1; i < n; i++) if (③) A[p++] = A[i]; n = p; int ans = 0, r = 0; int q = 0; while (r < m) { while (④) q++; ⑤; ans++; } cout << ans << endl; return 0; }
正确答案：完善程序①答案：A[j].a<A[j-1].a（按左端点升序）。核心：区间排序。
试卷来源：2020 CSP-J入门级（第一轮）C++真题