AcWing 905. 区间选点
原题链接
简单
作者:
xinyi127
,
2023-02-14 20:26:45
,
所有人可见
,
阅读 154
贪心
贪心题目
- 涉及区间的贪心题目一般都是排序,要么根据左端点排序,要么根据右端点排序,或者双关键字排序。
- 关于贪心的题目:
如果数据在 1e5,大概率是排序,$O(nlog(n))$ 的做法。
如果数据在 1e6,大概率是扫描一遍,$O(n)$ 的做法。
如果数据在 1e3,大概率是两重循环,$O(n2)$ 的做法。
如果数据在 1e2,大概率是三重循环,$O(n3)$ 的做法。
两种做法
- 为什么不能用左端点排序?这里需要走出一个误区,是可以根据左端点排序的,但是不同的排序方式要对应不同的处理方法。根据右端点排序可以保证当前所维护的区间范围是不随后续新覆盖区间而改变的,而左端点排序则不能保证。例如有两个区间
[1, 5]
、 [2, 3]
,假如按照右端点排序,首先遍历 [2,3]
,然后遍历 [1, 5]
,在这个过程中所维护的区间就是 [2, 3]
。而根据左端点排序,先遍历 [1, 5]
,然后遍历 [2, 3]
在这个过程中为了保证两个区间可以彼此覆盖,实际所维护的区间由 [1, 5]
变为了 [1, 3]
,但我们所记录的仍然是 [1, 5]
,所以需要单独处理这种情况。
- 这道题根据右端点排序,然后逐步遍历每个区间,查看是否被 已记录的区间 的右端点覆盖就可以了。
- 区间选点的本质是从 n 个区间中找出 ans 个两两之间没有交集的区间。
法一:右端点排序(常规做法)
贪心 c++ 234ms
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 100010, M = N * 2;
int n, d;
PII p[N];
bool cmp(PII a, PII b)
{
if (a.second == b.second) return a.first < b.first;
return a.second < b.second;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &p[i].first, &p[i].second);
sort(p + 1, p + n + 1, cmp);
int ans = 0, l = -0x3f3f3f3f3f;
for (int 1; i <= n; i ++ )
{
if (p[i].first > l)
{
ans ++;
l = p[i].second;
}
}
cout << ans;
return 0;
}
法二:根据左端点排序
贪心 c++ 236ms
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 100010, M = N * 2;
int n, d;
PII p[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &p[i].first, &p[i].second);
sort(p + 1, p + n + 1);
int ans = 0, l = -0x3f3f3f3f;
for (int i = 1; i <= n; i ++ )
{
if (p[i].first > l)
{
ans ++;
l = p[i].second;
}
else l = min(l, p[i].second);
}
cout << ans;
return 0;
}