XFZ开了一家餐馆。某一天,有n个人到XFZ的餐馆吃饭。每个人到餐馆的时间为ai,离开时间为bi。XFZ想知道最多有多少人同时在餐馆吃饭。这道题代码这么写
时间: 2023-05-19 21:02:02 浏览: 57
可以使用贪心算法,将所有人到餐馆和离开餐馆的时间按照时间顺序排序,然后遍历这个序列,记录当前同时在餐馆的人数的最大值即可。具体实现可以参考以下代码:
```
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100000;
struct Event {
int time;
int type; // 0表示到达,1表示离开
bool operator<(const Event& other) const {
return time < other.time || (time == other.time && type < other.type);
}
} events[MAXN * 2];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
events[i * 2] = {a, 0};
events[i * 2 + 1] = {b, 1};
}
sort(events, events + n * 2);
int ans = 0, cnt = 0;
for (int i = 0; i < n * 2; i++) {
if (events[i].type == 0) {
cnt++;
ans = max(ans, cnt);
} else {
cnt--;
}
}
cout << ans << endl;
return 0;
}
```
这个算法的时间复杂度为O(nlogn),其中n为人数。