贪心
tip
没有常规的模板，也没有常规的套路，能写出来全是玄学
区间问题
区间选点
算法思路
- 将每个区间按右端点从小到大排序
- 从前往后依次枚举每个区间：如果当前区间中已经包含点，则直接pass，否则，选择当前区间的右端点
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range
{
int l,r;
bool operator<(const Range &W)const
{
return r < W.r;
}
}range[N];
int main()
{
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, ed = -2e9;
for(int i=0;i<n;i++)
if(range[i].l > ed)
{
res ++;
ed = range[i].r;
}
printf("%d\n",res);
return 0;
}
最大不相交区间数量
tip
问题的做法和上一个问题的做法一模一样 代码也一摸一样
区间分组
tip
- 将所有区间按左端点从小到大排序
- 从前往后处理每个区间：判断能否将其放到某个现有的组