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

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

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

1 Like