题目描述
使用贪心策略,选择最大化右端点的区间,同时确保覆盖整个区间
补充一下不成立的条件还有无法构成全覆盖区间,也就是剩余的所有 l 都没有小于st
会触发以下条件
if (r < st)
{
res = -1;
break;
}
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
struct Range
{
int l, r;
bool operator< (const Range &w) const
{
return l < w.l;
}
}range[N];
int n;
int st, ed;
int main()
{
scanf("%d%d", &st, &ed);
scanf("%d", &n);
for (int i = 0; i < n; i ++)
{
int l, r;
scanf("%d%d", &l, &r);
range[i] = {l, r};
}
sort(range, range + n);
int res = 0;
bool success = false;
for (int i = 0; i < n; i ++ )
{
int j = i;
int r = -2e9;
while (j < n && range[j].l <= st)
{
r = max(r, range[j].r);
j ++ ;
}
if (r < st) // 所有 l 都大于 st,是无法全覆盖的情况
{
res = -1;
break;
}
res ++ ;
if (r >= ed) // 结束计数
{
success = true;
break;
}
st = r;
i = j - 1;
}
if (!success) res = -1;
printf("%d\n", res);
return 0;
}