题意:
给定n个乘客的乘车区间,问他们乘车最坏情况下需要座位数和最优情况下需要座位数
思路:
这个最坏情况是每个人任选座位,不管有冲突的怎么选,每个人都能做得下;这里我们考虑的是每个人乘车区间会跟别的几个人冲突,那加上他自身的个数选个最大的就是至少需要的座位数
显然不能n^2求解,所以我们按区间左值从小到大排序: 先从左往右遍历,每个区间的右值更新到树状数组里,对于当前区间,我们只要计算树状数组中大于当前区间左值的个数就好了; 然后从右往左遍历,清空树状数组后储存后面每个区间的左值,然后对于当前区间,查找树状数组中小于当前区间右值的个数,,,这样得出来的就是每个区间跟其有交集的个数
对于最优的情况,每个区间覆盖的时间点都更新一下,看某个时间点更新的最大次数就是答案,这个的话相当于线段树区间更新,但是这里有个简单的做法,就是更新区间是,区间左值更新正值,区间右值点更新负值,这样求前缀和得到的就是某个点的更新次数;
#include<iostream>
#include <cstdio>
#include<algorithm>
#include <cstring>
#include <set>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
const int maxn = 2e5 + 7;
const int maxd = 1e5 + 7;
int n;
int ans1 = 0, ans2 = 0;
struct node {
int l, r;
}a[maxn];
bool cmp(node a, node b) {
if(a.l == b.l) return a.r < b.r;
return a.l < b.l;
}
int sum[maxd] = {0};
int c[maxd];
int ans[maxn];
int lowbit(int x) {
return (x&-x);
}
int sum_(int x) {
int res = 0;
while(x>0) {
res += c[x];
x -= lowbit(x);
}
return res;
}
void add(int x, int v) {
while(x<=(maxd-1)) {
c[x] += v;
x += lowbit(x);
}
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d%d", &a[i].l, &a[i].r);
}
for(int i = 1; i <= n; ++i) {
sum[a[i].l]++;
sum[a[i].r]--;
}
int t = 0;
for(int i = 1; i < maxd; ++i) {
t += sum[i];
ans2 = max(ans2, t);
}
sort(a+1,a+1+n,cmp);
memset(c, 0, sizeof c);
memset(ans, 0, sizeof ans);
for(int i = 1; i <= n; ++i) {
ans[i] += (sum_(maxd-1) - sum_(a[i].l));
add(a[i].r, 1);
}
memset(c, 0, sizeof c);
for(int i = n; i > 0; --i) {
ans[i] += (sum_(a[i].r-1));
add(a[i].l, 1);
}
for(int i = 1; i <= n; ++i) {
ans1 = max(ans1, ans[i]);
}
printf("%d %d\n", ans1+1, ans2);
return 0;
}