AcWing 907. 区间覆盖
原题链接
简单
作者:
我要出去乱说
,
2021-01-31 17:42:57
,
所有人可见
,
阅读 314
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range
{
int l, r;
bool operator< (const Range& t) const
{
return l < t.l;
}
}range[N];
int main()
{
int st, ed;
cin >> st >> ed;
cin >> n;
for (int i = 0; i < n; i ++ )
{
int l, r;
cin >> 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, r = -2e9;
while (j < n && range[j].l <= st) //遍历找出所有左端点在st左边且右边最大的区间
{
r = max(r, range[j].r);
j ++ ;
}
if (r < st) //最大值都小于线段左端点,说明无解
{
res = -1;
break;
}
res ++ ; //找到一个,结果加1
if (r >= ed) //已经完全覆盖,退出循环
{
success = true;
break;
}
st = r;
i = j - 1; //没有这步也可以,但会慢很多
}
if (!success) res = -1;
cout << res << endl;
return 0;
}