CSES - Restaurant Customers

In this problem, we're given $n$ intervals with distinct start and end points, and we want to find the maximum number of intervals overlapping some point.

Solution

Let's transform the problem by assigning start points the value $1$ and end points the value $-1$. Then, if we put the start and end points into an array and sort them, the problem becomes: "given an array of values, find the maximum sum at some prefix in the array." This can be done by looping over the array and storing a running sum.

Code

1#include <bits/stdc++.h> 
2using namespace std;
3
4using ll = long long;
5
6using vi = vector<int>;
7#define pb push_back
8#define rsz resize
9#define all(x) begin(x), end(x)
10#define sz(x) (int)(x).size()