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

We can use prefix sums to determine the number of intervals that cover any particular point, and then find the maximum number in the sum.

A naïve approach is to create an array $\texttt{ctr}$, where $\texttt{ctr}[i]$ is the number of intervals that cover each point $i$. We can do this by looping through each interval $[a,b]$ and increasing $\texttt{ctr}[i]$ by $1$ for each index in $a \leq i \leq b$.

This results in a $\mathcal{O}(nV)$ time complexity (where $0 \leq a \leq b \leq V$), which easily times out (think what happens when the interval $[0, V]$ is queried $n$ times).

We can do better. It's easy to see that an increment of $x$ (before computation) in $\texttt{arr}[i]$ causes all subsequent $\texttt{prefix}[i...V]$ (after computation) to increase by $x$. We can also "undo" this operation by adding $-x$ to $\texttt{arr}[i]$. This concept can be conceptualized through increment and decrement points. An increment point increases (and decrement decreases) all subsequent cells. Note that our decrement point is located at $B+1$ because the interval is inclusive - decrementing at point $B$ turns the interval to $[A, B)$.

Example 1: Add two to each point in the interval $[2, 4]$

Our array after adding 2 at our increment (start) point (before computation)

Our prefix sum after adding 2 at our increment (start) point (and computing).

Our prefix sum after subtracting 2 at our decrement point (and computing).

Observe that this works for multiple intervals.

Example 2: Add two to each point in $[2, 4]$ and one to each point in $[1, 3]$

Adding interval $[2, 4]$ with increment point at $2$ and decrement at $4+1=5$

Adding interval $[1, 3]$ with increment point at $1$ and decrement at $3+1=4$

After computation

In this problem, our $x$ is fixed at $1$. As a result, when we encounter a starting point, we can increment by $1$, and for an endpoint, decrement by $1$. We actually cannot compute the prefix sum array directly since $V \leq 10^9$, and we will run out of memory when creating an array of size $V$.

Instead, we can either coordinate compress and compute the prefix sum over interesting intervals or sweep over the intervals while maintaining a running prefix sum.

Implementation 1

If we put the start and end points into a list and sort them, all we need to do is find the max sum of values over all prefixes of the list.

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> times;
	for (int i = 0; i < n; i++) {
		int start, end;
		cin >> start >> end;

Copy
import java.io.*;
import java.util.*;

public class Customers {
	public static void main(String[] args) throws IOException {
		BufferedReader read =
		    new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(read.readLine());

		int[][] times = new int[2 * n][];

Copy
import java.io.*;
import java.util.*;

public class Customers {
	public static void main(String[] args) throws IOException {
		BufferedReader read =
		    new BufferedReader(new InputStreamReader(System.in));
		TreeMap<Integer, Integer> times = new TreeMap<>();
		int n = Integer.parseInt(read.readLine());
		for (int i = 0; i < n; i++) {

Copy
times = []
for _ in range(int(input())):
	start, end = map(int, input().split())
	times.append((start, 1))
	times.append((end, -1))

times.sort()

curr_ppl = 0
max_ppl = 0

Copy
# Stores the change in the number of people at a specific time
tmap = dict()
times = []

for _ in range(int(input())):
	start, end = input().split()
	start = int(start)
	end = int(end)
	# tmap is 1 when person enters, -1 when person leaves
	tmap[start] = 1

Implementation 2

Coordinate compress interval endpoints and only compute the prefix sum array for interesting intervals.

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> times;
	for (int i = 0; i < n; i++) {
		int start, end;
		cin >> start >> end;

Copy
n = int(input())

times = []

for _ in range(n):
	start, end = map(int, input().split())
	times.append((start, 1))
	times.append((end + 1, -1))

times.sort()