(最小区间覆盖)给出n个区间,第i个区间的左右端点是[ai, bi]。现在 要在这些区间中选出若干个,使得区间[0,m]被所选区间的并覆盖(即每 一个0≤i≤m都在某个所选的区间中)。保证答案存在,求所选区间个数 的最小值。
输入第一行包含两个整数n和m(1≤n≤5000, 1≤m≤10^9 )
接下来n行,每行两个整数ai,bi(0≤ai, bi ≤ m)。
提示:使用贪心法解决这个问题。先用0(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[j].b < A[j -1] .b
A[j].b > A[j -1].b
A[ j] .a < A[ j - 1] .a
A[j] .a > A[j -1].a
②处应填()
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;
③处应填()
A[i].b < A[p - 1].b
A[i].b > A[i - l].b
A[i].b > A[p - 1].b
A[i].b < A[i - 1].b
④处应填()
q + 1 < n && A[q + l].b <= r
q + 1 < n && A[q + l].a <= r
q < n && A[q].a <= r
q < n && A[q].b <= r
⑤处应填()
r = max(r, A[q + 1].a)
r = max(r, A[q].b)
r = max(r, A[q + 1].b)
q++