Help with CSES problem Restaurant Customers

I was trying to solve the problem at But, I am stuck. Don’t know what to do or how to approach, I tried sorting (because it falls in that category :laughing:) 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.:slightly_smiling_face:

1 Like

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.


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() {
int main() {
	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 += ? 1 : -1;
		ans = max(ans, x);
	cout << ans << endl;

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. :smile:

UPDATE: Got an AC by shifting focus from the intervals themselves to the points where the change occurs.:smile:

1 Like

simpler version with sorting …

int32_t main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ll n;
    vector<pair<int,bool>> v;
    ll x; ll y;
   	ll ans =0; ll maxx =0;
   	for(int i=0;i<v.size();i++){
   			maxx = max(ans,maxx);

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.

1 Like

Hey , Thanks for this @galencolin ,I also got stuck and this helps me in solving the problem… :innocent: