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

题目

（最小区间覆盖）给出 $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. q+1<n&&A[q+1].a<=r
• B. q+1<n&&A[q+1].b<=r
• C. q<n&&A[q].a<=r
• D. q<n&&A[q].b<=r

答案

A

题解

答案是 A：q+1<n&&A[q+1].a<=r。

贪心思路是：假设当前已经覆盖了区间 [0,r]，下一步就在所有左端点不超过 r 的区间中，选择右端点最大的一个，让覆盖范围尽量向右延伸。

前面的程序会先按左端点从小到大排序，再删除被前面区间包含的区间。这样，剩下的区间左端点有序，右端点也严格递增。因此，找到最后一个左端点不超过 r 的区间，就是本轮的最佳选择：

``cpp while (q + 1 < n && A[q + 1].a <= r) q++; r = A[q].b; // ⑤：更新覆盖范围 ans++; ``

这里检查的是下一个区间 q+1 能否接上，能接上才让 q 前进。循环结束后，q 恰好停在本轮应该选择的区间上。

• B、D 检查右端点，不能判断区间能否接上。
• C 检查当前区间后再 q++，会让 q 越过最后一个符合条件的区间，甚至越界。