区间覆盖
sort(a.begin(), a.end());
int ans = 0, las = s;
for (int i = 0; i < n; ++i) {
int j = i;
int r = -2e9;
while (j < n and a[j].first <= las) {
r = max(r, a[j].second);
j ++;
}
if (r >= las) {
ans ++, las = r;
} else {
cout << -1;
return 0;
}
if (las >= t) {
break;
}
i = j - 1;
}
las >= t ? cout << ans << '\n' : cout << -1;
问题简述
有若干备选区间,问能覆盖目标线段的最少区间。
贪心
标签:cout,覆盖,int,端点,区间,一题,las From: https://www.cnblogs.com/whose-dream/p/16875325.html对区间按左端点排序,对于当前已覆盖区间的右端点(初值为线段左端点)P,选取能覆盖P右端点最大的的区间,且将P更新为这个右端点, O(n)。