(最小区间覆盖)给出 n 个区间,第 i 个区间的左右

(最小区间覆盖)给出 n 个区间,第 i 个区间的左右端点是[ai,bi]。现在要在这些区间中选出若干个,使得区间 [0,m][0,m] 被所选区间的并覆盖(即每一个 0≤i≤m 都在某个所选的区间中)。保证答案存在,求所选区间个数的最小值。

输入第一行包含两个整数 n 和 m(1≤n≤5000, 1≤m≤109)。

接下来 n 行,每行两个证书 ai,bi(0≤ai,bi≤m)。

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

试补全程序。

#include <cstdio>
using namespace std;

int n, i;

int main() {
    scanf("%d", &n);
    for (i = ①; ② <= n; i ++) {
        ③ {
            printf("%d ", i);
            n = n / i;
        }
    }
    if (④) {
        printf("%d ", ⑤);
    }
    return 0;
}

③ 处应填( )

答案
A

题目信息

题号:672
题型:单选题
知识点:CSP考试
难度:普通