区间选点
原题链接：905. 区间选点 - AcWing题库
在所给的多个区间里选点，使得选得最少的点覆盖所有区间 端点也算
思路
先对样例试一试
从当前看哪种情况最佳？ 一个点覆盖最多的区间 选哪个点可以覆盖最多区间？ 只要区间不完全分开，就可以选有重叠的区间的右端点来覆盖多个区间
实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
//利用重载，也可以写cmp
struct Range{
int l, r;
bool operator < (const Range &w) const
{
return r < w.r;
}
}r[N];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> r[i].l >> r[i].r;
}
//按右端点排序
sort(r, r + n);
int rd = -2e9, ans = 0;
for(int i = 0; i < n; i ++)
{
if(r[i].l > rd)
{
ans ++;
rd = r[i].r;
}
}
cout << ans << endl;
return 0;
}另一种说法
原题链接：908. 最大不相交区间数量 - AcWing题库
几乎一致的思路 要选最大的不交叉区间，则区间的左端点不能小于前一个的右端点，要尽可能多，就从头开始选（贪心）
区间分组
原题链接：906. 区间分组 - AcWing题库
对所给区间分组，要求没有交集，分组尽可能少
思路
贪心的做
对区间排序，按需求，我要将尽可能多的区间分为一组，那么遍历时应该是考虑尽可能多的区间能不能并到现有的组里，也就是看左端点与当前的右端点有没有交集，要尽可能多，那就左端点从小看到大，找可以合并成一组的——左端点排序
然后考虑贪心着做对不对
从两个角度看，但凡能有两种特殊情况满足上述式子，就可以证明大于等于小于等于都成立
首先找的是最小的分组数，则 一定成立
特殊情况证明大于等于： 当每个区间都要各分一组的时候，即下一个的左端点都小于当前的右端点 由于 ans 一定是所有的区间的分组数，其值一定得是大于等于所有区间数才可能给所有区间分组，所以 得证
实现
要维护一个数组，用来存下每组的右端点值，同时数组的大小就是分组数
用小根堆
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
struct Range{
int l, r;
//左端点排序
bool operator < (const Range &w)const{
return l < w.l;
}
}r[N];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> r[i].l >> r[i].r;
}
sort(r, r + n);
//小根堆
priority_queue<int, vector<int>, greater<int>> heap;
for(int i = 0; i < n; i ++)
{
//如果左端点小于最小右端点或还没分组
if(heap.empty() || r[i].l <= heap.top())
{
//建新组
heap.push(r[i].r);
}
else
{
//加到当前右端点最小的组
heap.pop();
heap.push(r[i].r);
}
}
cout << heap.size() << endl;
return 0;
}实际上实现可以可以是任选一组添加，这里实现为加到最小的一组
- 更符合贪心思想
- 其实没有证明任何一组都可以
区间覆盖
原题链接：907. 区间覆盖 - AcWing题库
给定可选区间与要求区间，要求找最少的区间覆盖要求区间
思路
贪心着做
每次选肯定要选能覆盖最多的，那就按左端点排序，选右端点到最远的，同时与前面选的区间有交集的区间
证明
小于等于：所选必是所有可能选法之一，答案要求最小，必然小于等于
大于等于： 在第一处不一样的地方——如果答案选了右端点比思路选的近的（不可能远，因为思路选最远），那么其后面要是有更优的选法，思路当前选的这个区间一定能覆盖到之后选的区间的左端点，而且每次都可以
- 选短再选短，则思路选法更优
- 选短再选长，必覆盖得到，思路更优
- 都选长，则与思路一致 理解着明白大于等于
实现
- 左排序
- 找左端点小于等于当前右端点的右端点最大的区间
- 更新右端点
- 用双指针找
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 +10;
struct Range{
int l, r;
bool operator < (const Range &w)const{
return l < w.l;
}
}r[N], ed;
int main()
{
cin >> ed.l >> ed.r;
int n;
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> r[i].l >> r[i].r;
}
sort(r, r + n);
int cnt = 0, st = ed.l;
bool flag = 0;
for(int i = 0; i < n; i ++)
{
int j = i, now_r = -2e9;
//起始满足左端点小于区间左端点，然后选最长
while(j < n && r[j].l <= st)
{
now_r = max(now_r, r[j].r);
j ++;
}
//如果交不上了
if(now_r < st)
break;
if(now_r >= ed.r)
{
flag = 1;
cnt ++;
break;
}
cnt ++;
//双指针，当前j找过的都不用找
i = j - 1;
st = now_r;
}
if(flag) cout << cnt << endl;
else cout << "-1" << endl;
return 0;
}