CSP-J 2020 第一轮 第 39 题：最小区间覆盖：①处应填

题目

（最小区间覆盖）给出 $n$ 个区间，第 $i$ 个区间的左右端点是 $[a_i,b_i]$。现在要在这些区间中选出若干个，使得区间 $[0, m]$ 被所选区间的并覆盖（即每一个 $0\leq i\leq m$ 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数 $n$ 和 $m$ （$1\le n \le 5000,1\le m \le 10^9$）

接下来 $n$ 行，每行两个整数 $a_i,b_i$ （$0\le a_i,b_i \le m$）。

提示：使用贪心法解决这个问题。先用 $O(n^2)$ 的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

   #include <iostream>

   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; i++)
     for (int j = 1; j < n; j++)
     if (①)
         {
           segment t = A[j];
           ②
         }
   }

   int main()
   {
     cin >> n >> m;
     for (int i = 0; i < n; i++)
       cin >> 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. A[j].b>A[j-1].b
• B. A[j].a<A[j-1].a
• C. A[j].a>A[j-1].a
• D. A[j].b<A[j-1].b

答案

B

题解

答案是 B：A[j].a < A[j-1].a。

这道题的贪心思路是：假设已经覆盖到位置 r，就在所有左端点不超过 r 的区间中，选择右端点最大的那个。这样每选一个区间，都能让覆盖范围向右延伸得最远。

因此，先把区间按左端点从小到大排序，方便依次寻找能与当前覆盖范围接上的区间。

程序中比较的是相邻的 A[j-1] 和 A[j]。如果后一个区间的左端点更小，就应交换它们，所以①填：

``cpp A[j].a < A[j-1].a ``

为什么这样贪心正确？在同样能接上的区间中，右端点越大，留给后续覆盖的部分越少，所需区间数就不会更多。