第一问,对每名学生,计算与其来馆时间交集非空的学生个数+1的值。这些值的最大值就是答案。
第二问,对每个时刻,计算有多少学生在馆,取最大值即为答案。
正确性请自行思考,代码见 AC 提交,时间复杂度
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 202020;
int n, pre[MAXN], suf[MAXN], cc[MAXN], ans1, ans2, l[MAXN], r[MAXN];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d%d", &l[i], &r[i]);
cc[l[i]]++, cc[r[i]]--;
pre[r[i]]++, suf[l[i]]++;
}
for(int i = 1; i < MAXN; ++i) {
cc[i] += cc[i - 1];
pre[i] += pre[i - 1];
ans2 = max(ans2, cc[i]);
}
for(int i = MAXN-2; i >= 0; --i)
suf[i] += suf[i + 1];
for(int i = 1; i <= n; ++i)
ans1 = max(ans1, n - pre[l[i]] - suf[r[i]]);
printf("%d %d\n", ans1, ans2);
return 0;
}