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

题目

（最小区间覆盖）给出 $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[i].b>A[p-1].b
• B. A[i].b<A[i-1].b
• C. A[i].b>A[i-1].b
• D. A[i].b<A[p-1].b

答案

A

题解

第③题选 A：A[i].b > A[p-1].b。

排序后，区间按左端点从小到大排列。这段代码是在筛掉被前面区间包含的区间：

• p 表示目前保留的区间个数。
• A[p-1] 是最后一个保留的区间。
• 只有当前区间的右端点更大，才把它保留下来。

因为已经有 A[p-1].a <= A[i].a，所以如果 A[i].b <= A[p-1].b，当前区间就完全包含在 A[p-1] 中，选它不会比选 A[p-1] 更好，可以丢弃。

因此应填： ``cpp if (A[i].b > A[p-1].b) A[p++] = A[i]; ``

注意要与 最后保留的区间 A[p-1] 比较，而不是 A[i-1]，因为前一个扫描过的区间可能已经被丢弃。筛选后，保留区间的右端点严格递增，方便后续贪心选择。