Notice: Undefined index: name in /usr/www/lib/views/home/viewtitle.html on line 188
-完善程序 第 20 题
(最小区间覆盖)给出n个区间,第i个区间的左右端点是$[a_i, b_i]$。现在要在这些区间中选出若干个,使得区间[0, m]被所选区间的并覆盖(即每一个$0≤i≤m$都在某个所选的区间中)。保证答案存在,求所选区间个数的最小值。 输入第一行包含两个整数$n$和$ m (1≤n≤5000, 1≤m≤10^9)$。 接下来n行,每行两个整数$a_i, b_i (0≤ai, bi≤m)$。 提示:使用贪心法解决这个问题。先用$θ(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;
}
● 单选题
第 1 题 ①处应填()
第 2 题 ②处应填()
第 3 题 ③处应填()
第 4 题 ④处应填()
第 5 题 ⑤处应填()

解答部分以后会开放。