AcWing 906. 区间分组
原题链接
简单
作者:
ywt51
,
2023-05-24 17:27:43
,
所有人可见
,
阅读 32
算法1:贪心-区间分组(476ms) $O(nlogN)$
//每个区间必然属于某一个组,对每一个组看是否能加入之前的组,之前组的右端点小于 该区间的左端点可加入
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1E5+10;
PII a[N];
int n;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++ i) scanf("%d%d", &a[i].first, &a[i].second);
sort(a, a+n);
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i < n; ++ i)
if (heap.empty() || heap.top() >= a[i].first) heap.push(a[i].second);
else {
heap.pop();
heap.push(a[i].second); //更新该区间的最靠右的右端点
}
printf("%d", (int)heap.size());
return 0;
}
算法2:离散化-差分(1041ms) $O(nlogN)$
//离散化-差分,求前缀和,被覆盖最多的就是最小组数
#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
int n, res;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++ i) {
int l, r;
scanf("%d%d", &l, &r);
mp[l] ++;
mp[r+1] --;
}
int s = 0; //求前缀和,过程中维护出最大值
for (auto [k, v] : mp) {
s += v;
res = max(res, s);
}
printf("%d", res);
return 0;
}