AcWing 905. 区间选点
原题链接
简单
作者:
描绘一抹色
,
2024-10-22 13:34:16
,
所有人可见
,
阅读 1
//贪心: 每次都作出(选择)最符合当前利益的选择
//本题问题: 区间贪心, 给出几段区间(可有交集的区间),在区间上选点, 选择最少的点, 使每个区间都有点
//选用模板: 贪心, 没有具体模板
//算法主要思想: 按区间左右端点排序 + 不断维护另一端点
// 排序: 贪心问题按左右端点排序大部分情况都可以
// 但不同的排序, 所需维护另一端点的方法也就不一样,尽量选择更好维护另一端点的方式进行排序
// 维护另一端点: 这里按左端排序来维护, 遍历每个区间 && 用一个变量不断更新迭代目前遍历到的区间右端点最大值
// 如果当前枚举到的区间的左端点大于变量记录的最大右端点, 那么就需要再加一个点, 保证每个区间都有点
// 如果小于变量记录的最大右端点, 那么就不需要加入一个点, 因为这个点在上个枚举到的区间右边, 可以保证加入当前区间每个区间都有点
// 总结: 这里贪心思想在于把每个点都放在最符合当前利益的位置(区间最右边),使其能覆盖更多区间,在条件都能满足的情况下,越靠右边显然在之后就可能覆盖到更多区间
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
int INF = -2e9;
int n;
struct Edge
{
int l;
int r;
bool operator< (const Edge &W)const
{
return r < W.r;
}
}edges[N];
int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
{
int a, b;
cin >> a >> b;
edges[i] = {a, b};
}
sort(edges, edges + n);
// res维护了当前遍历到的区间最大右端点值
int res = INF;
// 需要多少点
int sum = 0;
for(int i = 0; i < n; i ++)
{
// 当前区间的左端点 > 以往区间右端点的最大值->需要再来一个点, 更新右端点
if(res < edges[i].l)
{
res = edges[i].r;
sum ++;
}
}
cout << sum << endl;
return 0;
}