②处应填()
(最小区间覆盖)给出n个区间,第1个区间的左右端点是[ai,bi]。现在要在这些区间中选出若干个,使得区间[8,m]被所选区间的并覆盖(即每一个0≤i≤m都在某个所选的区间中)。保证案存在,求所选区间个数的最小值。 输入第一行包含两个整数n和m(1≤n≤5008,1≤m≤109)接下来n行,每行两个整数ai,bi(0≤ai,bi≤m) 提示:使用贪心法解决这个问题。先用0(n2)的时间复杂度排序,然后贪心选择这些区间。
#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[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;