I was trying to solve the problem at CSES - Restaurant Customers. But, I am stuck. Don’t know what to do or how to approach, I tried sorting (because it falls in that category 
) then tried searching but nothing seems to work. Explanations (preferably with some intuition as to why it is correct) and code (if possible) are highly appreciated.
2 Likes
Keyword: coordinate compression
Intuition: here’s an example. Say you have exactly one interval: (2, 7). At time points 3, 4, 5, and 6, absolutely nothing changes. So you can say they’re all “equivalent” to the time point 2. The same goes for time points 8 to \infty - they all end up being equivalent. So you can compress the input so you only consider the time points where something changes, then use prefix sums/whatever to solve the new problem since all of the values are at most 2n.
9 Likes
I used a priority queue of a pair<int,bool> wherein bool true would mean entering and false would mean exiting. Also the int I stored was negative of time.
Then i simulated the process, always storing max people at a time in the restaurant.
Here’s the code:
#include <bits/stdc++.h>
using namespace std;
#define M1 1000000007
#define M2 998244353
#define ll long long
#define pll pair<ll,ll>
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define REPR(i,a,b) for(ll i=b-1;i>=a;i--)
#define forr(i,n) for(ll i=0;i<n;i++)
#define F first
#define S second
#define pb push_back
#define DB pop_back
#define mp make_pair
#define MT make_tuple
#define V(a) vector<a>
#define vi vector<ll>
#define endl '\n'
#define ce(ele) cout<<ele<<' '
#define cs(ele) cout<<ele<<'\n'
#define CASE(t) ll t; cin>>t; while(t--)
void FAST() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main() {
FAST();
ll n, a, b;
cin >> n;
priority_queue<pair<int, bool>> q;
while (n--) {
cin >> a >> b;
q.push({ -a, true});
q.push({ -b, false});
}
ll x = 0, ans = 0;
while (!q.empty()) {
x += q.top().second ? 1 : -1;
q.pop();
ans = max(ans, x);
}
cout << ans << endl;
}
4 Likes
Thanks @galencolin and @adityat25 for the quick response. I’ll try solving the problem using the hint provided by @galencolin, and then if at all I am stuck again, I’ll have a look at the code provided by @adityat25. 
UPDATE: Got an AC by shifting focus from the intervals themselves to the points where the change occurs.
2 Likes
simpler version with sorting …
int32_t main() {
FAST_IO;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ll n;
cin>>n;
vector<pair<int,bool>> v;
ll x; ll y;
while(n--){
cin>>x;cin>>y;
v.pb(make_pair(x,true));
v.pb(make_pair(y,false));
}
sort(v.begin(),v.end());
ll ans =0; ll maxx =0;
for(int i=0;i<v.size();i++){
if(v[i].second==true){
ans++;
maxx = max(ans,maxx);
}else{
ans--;
}
}
cout<<maxx<<endl;
}
Also what i understand from galen’s reply is that whenever something gets change you keep track of that thing. like if customer is coming you do +1 if going you do -1.
then at last you do prefix sum on 2*n elements and find the max out of that which is your answer.
hope i am correct if not do tell me.
2 Likes
