簡易題敘#
一個餐廳有 \(n (1 \le n \le 2 \times 10^5)\) 個顧客，給你他們到跟離開的時間，求人最多的時候有多少客人。
範例測資：
- 輸入
3
5 8
2 4
3 9
- 輸出
2
概念講解#
這題跟教學文章上寫的線段覆蓋範例基本上概念一模一樣！
先開一個 vector \(P\) 紀錄進出時間，pair 的 first 記時間，second 記進（\(1\)）或出（\(-1\)）。
vector<pair<int,int>> P;
.
.
.
for(int i = 0; i < n; i++){
cin >> l >> r;
P.push_back({l, 1});
P.push_back({r, -1});
}
排序之後處理每個線段端點的客人數量加減，每改變一次就要跟答案取max。
for(auto p : P){
now += p.second;
ans = max(ans, now);
}
範例程式碼#
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
vector<pii> P;
int n, l, r, now, ans;
signed main(){
cin >> n;
for(int i = 0; i < n; i++){
cin >> l >> r;
P.push_back({l, 1});
P.push_back({r, -1});
}
sort(P.begin(), P.end());
for(auto p : P){
now += p.second;
ans = max(ans, now);
}
cout << ans;
}
