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

题目

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

答案

B

题解

答案是 B：r = max(r, A[q].b)。

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

程序前面的排序和筛选会去掉被其他区间包含的无用区间，使剩余区间的左右端点依次递增。因此，④处不断让 q 后移，找到当前可以衔接的最后一个区间，它也是这些候选区间中右端点最大的。

找到后，就更新覆盖范围：

``cpp r = max(r, A[q].b); ``

然后 ans++，表示又选了一个区间，直到 r >= m。

A 中的 q+1 对应下一个区间，它可能与当前覆盖范围之间存在空隙，也可能越界；C 使用左端点，无法表示新的覆盖范围；D 没有更新 r。