Restaurant Customers

簡易題敘

一個餐廳有 $n (1 \le n \le 2 \times 10^5)$ 個顧客，給你他們到跟離開的時間，求人最多的時候有多少客人。

範例測資：

輸入

輸出

概念講解

這題跟教學文章上寫的線段覆蓋範例基本上概念一模一樣！

先開一個 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;
}