AcWing 907. 区间覆盖-超详细注释
原题链接
简单
作者:
乙烯一克一克一克
,
2022-06-06 23:44:47
,
所有人可见
,
阅读 218
/**
* 1. 将所有区间按左端点从小到大排序
* 2. 从前往后依次枚举每个区间,在所有能覆盖start的区间中,选择右端点最大区间
* 3. 将start更新为右端点最大值
**/
#include <iostream>
#include <algorithm>
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 main()
{
int n, 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 flag = false;
// 开始寻找覆盖[st, ed]的区间
for(int i = 0; i < n; i ++)
{
// 使用双指针
int j = i, r = -2e9;
while (j < n && range[j].l <= st)
{
// 取所有左端点大于st 并且区间长度最大的区间也就是r最大
r = max(r, range[j].r);
j ++;
}
// 如果找遍了后面的区间r的最大都无法覆盖st 则无解
if (r < st)
{
res = -1;
break;
}
else // 寻找成功
{
res ++;
}
// 找到方案覆盖[st, ed] 提前退出
if(r >= ed)
{
flag = true;
break;
}
// 找到j之后 从j的下一个位置开始寻找继续覆盖的区间 并且把st初始成当前找到覆盖区间的r
i = j - 1;
st = r;
}
if (flag) cout << res;
else cout << "-1";
return 0;
}