AcWing 1750. 救生员 - cpp - 差分 + 枚举
原题链接
简单
作者:
Antonioxv
,
2022-02-20 14:04:45
,
所有人可见
,
阅读 175
cpp
#include <bits/stdc++.h> // 万能头文件
using namespace std;
const int N = 110, T= 1010;
int l[N], r[N], diff[T];
int n;
void insert(int left, int right, int val){
diff[left] += val;
diff[right] -= val;
}
int main(void){
// I/O
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> l[i] >> r[i];
insert(l[i], r[i] , 1);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int sum = 0, val = 0;
diff[l[i]]--, diff[r[i]]++;
for (int j = 0; j < 1000; j++) {
val += diff[j];
if (val > 0) sum++;
}
diff[l[i]]++, diff[r[i]]--;
ans = max(ans, sum);
}
cout << ans << endl;
return 0;
}