A42031. $（最小区间覆盖）给出 n 个区间，第 i 个区间的左右端点是[ai,bi]。现在要在这些区间中选出若干个，使得区间 [0,m][0,m] 被所选区间的并覆盖（即每一个 0\leqi\leqm 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。输入第一行包含两个整数 n 和 m（1\leqn\leq5000, 1\leqm\leq109）。接下来 n 行，每行两个证书 ai，bi（0\leqai，bi\leqm）。提示：使用贪心法解\dots$

单选题困难

知识点

贪心算法区间覆盖排序

题目描述

（最小区间覆盖）给出 n 个区间，第 i 个区间的左右端点是[ai,bi]。现在要在这些区间中选出若干个，使得区间 [0,m][0,m] 被所选区间的并覆盖（即每一个 0\leqi\leqm 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。 输入第一行包含两个整数 n 和 m（1\leqn\leq5000, 1\leqm\leq109）。 接下来 n 行，每行两个证书 ai，bi（0\leqai，bi\leqm）。 提示：使用贪心法解决这个问题。先用 Θ(n^2) 的时间复杂度排序，然后贪心选择这些区间。 试补全程序。 ② 处应填（ ）

A[j + 1] = A[j]; A[j] = t;

A[j - 1] = A[j]; A[j] = t;

A[j] = A[j + 1]; A[j + 1] = t;

A[j] = A[j - 1]; A[j - 1] = t;

上一题下一题