 # Help with CSES problem Restaurant Customers

I was trying to solve the problem at https://cses.fi/problemset/task/1619. 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. 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.

4 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;
}

3 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. 1 Like