CSES – Restaurant Customers

題目連結

題意

有 n 組客人來餐廳用餐，第 i 組客人進去和離開的時間用 a[i], b[i] 表示，最多同時有幾組客人在餐廳裡面?

解題方法

利用一個 vector <pair<int,int> > 把區間拆成開頭及結尾，利用 pair 第二個 true / false 紀錄是開頭還是結尾。將 vector 照排序完後，從小到大開始跑，每次遇到開頭進入的人數就加一，遇到結尾就減一。只要找到總和出現過的最大值就是答案。

    int n;
    cin >> n;
    vector <pair<int,bool> > v;
    for(int i = 0;i < n;i++){
        int a, b;
        cin >> a >> b;
        v.push_back({a,true});
        v.push_back({b,false});
    }
    sort(v.begin(), v.end());
    int ans = 0, sum = 0;
    for(int i = 0;i < v.size();i++){
        if(v[i].second) sum++;
        else sum--;
        ans = max(ans, sum);
    }
    cout << ans << '\n';