Restaurant Customers

題目說測資會到10**9，接近好幾GB了，所以本篇介紹兩種寫法，如果測資小的話可以考慮用第一種寫法。

想法 – 1

差分, 前綴是啥可以參考這篇 : https://hackmd.io/@HyC-1029/By-o9OAoyg

想法是:透過差分來標記區間[a:b]內有人，然後再用前綴和將正確人數還原出來。

MAX = 2*(10**5)
diff = [0] * (MAX+10)
n = int(input())

for _ in range(n): # 差分標記
    a,b = map(int, input().split())
    diff[a] += 1
    diff[b+1] -=1
 
p = [0] * (MAX+1) # 前綴還原
for i in range(1, MAX+1):
    p[i] = p[i-1] + diff[i]
print(max(p))

// 小心如果測資>10**6的話就會爆炸

想法 – 2

因為CSES的測茲有一個20,000，兩個迴圈來回就直接超時了(記憶體也爆掉)，

所以改是看看用C++線性搜。

一樣跟差分的想法，只要有人我就+1來計算進場人數，不過最後是一直比對 max()。

假設現在有一個input是

(1, 4)
(2, 5)
(7, 8)

我們用pair(a,x)將這筆資料存到vector中，a表時間，x表進場人數，會變

vector= {
{1, +1}, // 1點來一人
{2, +1},
{4, -1}, // 4點走一人
{5, -1},
{7, +1},
{8, -1}
}

接著再透過累加的方式線性搜

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
vector<pair<int, int>> li;

int main() {
    io;
    int n,a, b;;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> a >> b;
        li.push_back({a, 1});
        li.push_back({b, -1});
    }

    sort(li.begin(), li.end());// 按進場時間排序

    int cur = 0, ans = 0;
    for (auto [t, c] : li) {
        cur += c;
        ans = max(ans, cur);
    }

    cout << ans << '\n';
}