Restaurant Customers

Solución

Explicación

En este problema nos dan $n$ intervalos con puntos de inicio y fin distintos, y queremos hallar el máximo número de intervalos que se solapan en algún punto.

Podemos usar sumas de prefijos para determinar el número de intervalos que cubren cualquier punto particular, y luego hallar el máximo en la suma.

Un enfoque ingenuo es crear un arreglo $\texttt{ctr}$ , donde $\texttt{ctr}[i]$ es el número de intervalos que cubren cada punto $i$ . Podemos hacerlo recorriendo cada intervalo $[a,b]$ e incrementando $\texttt{ctr}[i]$ en $1$ para cada índice en $a \leq i \leq b$ .

Esto da complejidad $\mathcal{O}(nV)$ (donde $0 \leq a \leq b \leq V$ ), que fácilmente da TLE (piensa qué pasa cuando el intervalo $[0, V]$ se consulta $n$ veces).

Podemos hacerlo mejor. Es fácil ver que un incremento de $x$ (antes de la computación) en $\texttt{arr}[i]$ hace que todos los $\texttt{prefix}[i...V]$ posteriores (después de la computación) aumenten en $x$ . También podemos “deshacer” esta operación sumando $-x$ a $\texttt{arr}[i]$ . Este concepto se puede conceptualizar mediante puntos de incremento y decremento. Un punto de incremento aumenta (y uno de decremento disminuye) todas las celdas posteriores. Nótese que nuestro punto de decremento está en $B+1$ porque el intervalo es inclusivo: decrementar en el punto $B$ convierte el intervalo en $[A, B)$ .

Ejemplo 1: Sumar dos a cada punto del intervalo $[2, 4]$

Nuestro arreglo después de sumar 2 en el punto de incremento (inicio) (antes de la computación)

Nuestra suma de prefijos después de sumar 2 en el punto de incremento (inicio) (y computar).

Nuestra suma de prefijos después de restar 2 en el punto de decremento (y computar).

Observemos que esto funciona para varios intervalos.

Ejemplo 2: Sumar dos a cada punto de $[2, 4]$ y uno a cada punto de

[1, 3]

Añadiendo el intervalo $[2, 4]$ con punto de incremento en $2$ y decremento en $4+1=5$

-2

Añadiendo el intervalo $[1, 3]$ con punto de incremento en $1$ y decremento en $3+1=4$

-1

-2

Después de la computación

En este problema, nuestro $x$ está fijo en $1$ . Por lo tanto, cuando encontramos un punto de inicio, podemos incrementar en $1$ , y para un punto de fin, decrementar en $1$ . En realidad no podemos computar el arreglo de sumas de prefijos directamente pues $V \leq 10^9$ , y nos quedaremos sin memoria al crear un arreglo de tamaño $V$ .

En su lugar, podemos o bien comprimir coordenadas y computar la suma de prefijos sobre intervalos interesantes, o barrer los intervalos manteniendo una suma de prefijos en ejecución.

Implementación 1

Si ponemos los puntos de inicio y fin en una lista y los ordenamos, todo lo que hay que hacer es hallar la suma máxima de valores sobre todos los prefijos de la lista.

Complejidad temporal: $\mathcal{O}(N\log N)$

C++JavaPython


#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;
		times.push_back({start, 1});
		times.push_back({end, -1});
	}
 
	sort(times.begin(), times.end());
 
	int curr_ppl = 0;
	int max_ppl = 0;
	for (const pair<int, int> &t : times) {
		curr_ppl += t.second;
		max_ppl = max(max_ppl, curr_ppl);
	}
 
	cout << max_ppl << endl;
}

Si usamos la misma implementación que la versión de C++, CSES dará veredicto TLE en el caso de prueba 6.


import java.io.*;
import java.util.*;
 
public class RestaurantCustomers {
	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][];
		for (int i = 0; i < n; i++) {
			StringTokenizer cus = new StringTokenizer(read.readLine());
			times[2 * i] = new int[] {Integer.parseInt(cus.nextToken()), 1};
			times[2 * i + 1] = new int[] {Integer.parseInt(cus.nextToken()), -1};
		}
 
		// Sort the array by time
		Arrays.sort(times, Comparator.comparingInt(t -> t[0]));
 
		int mostPpl = 0;
		int currPpl = 0;
		for (int[] t : times) {
			currPpl += t[1];
			mostPpl = Math.max(mostPpl, currPpl);
		}
 
		System.out.println(mostPpl);
	}
}

Para arreglarlo, podemos usar un TreeMap en lugar de un arreglo ordenado.


import java.io.*;
import java.util.*;
 
public class RestaurantCustomers {
	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++) {
			StringTokenizer cus = new StringTokenizer(read.readLine());
			times.put(Integer.parseInt(cus.nextToken()), 1);
			times.put(Integer.parseInt(cus.nextToken()), -1);
		}
 
		int mostPpl = 0;
		int currPpl = 0;
		for (int t : times.values()) {
			currPpl += t;
			mostPpl = Math.max(mostPpl, currPpl);
		}
 
		System.out.println(mostPpl);
	}
}


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
 
for t in times:
	curr_ppl += t[1]
	max_ppl = max(max_ppl, curr_ppl)
 
print(max_ppl)

Como todos los tiempos de llegada y salida son distintos, podemos guardar si un tiempo dado es una llegada o una salida, y ordenar todos los tiempos de llegada y salida en un solo arreglo.


# 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
	tmap[end] = -1
	times.append(start)
	times.append(end)
 
times.sort()
 
curr_ppl = 0
max_ppl = 0
 
# Iterate through all times to see the maximum amount of people
for t in times:
	curr_ppl += tmap[t]
	max_ppl = max(max_ppl, curr_ppl)
 
print(max_ppl)

Implementación 2

Comprimimos coordenadas de los extremos de los intervalos y solo computamos el arreglo de sumas de prefijos para intervalos interesantes.

Complejidad temporal: $\mathcal{O}(N\log N)$

C++PythonJava


#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;
		times.push_back({start, 1});
		times.push_back({end + 1, -1});
	}
 
	sort(times.begin(), times.end());
 
	int curr = 0;
	int at = 0;
	// Stores how much the # of people in the restaurant changes each time step
	vector<int> ppl_change(2 * n);
	// Compress the starting & ending events into a single array
	for (int i = 0; i < 2 * n; i++) {
		if (i == 0) {
			times[i].first = 0;
		} else if (times[i].first > curr) {
			at++;
			curr = times[i].first;
		}
		ppl_change[at + 1] += times[i].second;
	}
 
	// Build our prefix sum array
	vector<int> ppl_amt(2 * n + 1);
	for (int i = 1; i < 2 * n + 1; i++) {
		ppl_amt[i] = ppl_change[i - 1] + ppl_amt[i - 1];
	}
 
	// Our answer is just the maximum of the prefix sum array
	int max_ppl = 0;
	for (int i = 0; i < 2 * n + 1; i++) { max_ppl = max(max_ppl, ppl_amt[i]); }
 
	cout << max_ppl << endl;
}


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()
 
curr = 0
at = 0
 
# Stores how much the # of people in the restaurant changes each time step
ppl_change = [0] * (2 * n)
 
# Compress the starting & ending events into a single array
for i in range(2 * n):
	if i == 0:
		times[i] = (0, times[i][1])
	elif times[i][0] > curr:
		at += 1
		curr = times[i][0]
	ppl_change[at] += times[i][1]
 
# Build our prefix sum array
ppl_amt = [0] * (2 * n + 1)
for i in range(1, 2 * n + 1):
	ppl_amt[i] = ppl_change[i - 1] + ppl_amt[i - 1]
 
# Our answer is the maximum of the prefix sum array
max_ppl = max(ppl_amt)
 
print(max_ppl)


import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class RestaurantCustomers {
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(r.readLine());
		int n = Integer.parseInt(st.nextToken());
 
		ArrayList<int[]> times = new ArrayList<int[]>();
 
		for (int i = 0; i < n; i++) {
			int start, end;
			st = new StringTokenizer(r.readLine());
			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());
			times.add(new int[] {start, 1});
			times.add(new int[] {end + 1, -1});
		}
 
		times.sort((a, b) -> {
			int cmp = Integer.compare(a[0], b[0]);
			if (cmp != 0) return cmp;
			return Integer.compare(a[1], b[1]);
		});
 
		int curr = 0;
		int at = 0;
		// Stores how much the # of people in the restaurant changes each time step
		int[] ppl_change = new int[2 * n + 2];
		// Compress the starting & ending events into a single array
		for (int i = 0; i < 2 * n; i++) {
			if (i == 0) {
				times.get(i)[0] = 0;
			} else if (times.get(i)[0] > curr) {
				at++;
				curr = times.get(i)[0];
			}
			ppl_change[at + 1] += times.get(i)[1];
		}
 
		int[] ppl_amt = new int[2 * n + 1];
		for (int i = 1; i < 2 * n + 1; i++) {
			ppl_amt[i] = ppl_change[i - 1] + ppl_amt[i - 1];
		}
		int max_ppl = 0;
		for (int i = 0; i < 2 * n + 1; i++) { max_ppl = Math.max(max_ppl, ppl_amt[i]); }
 
		System.out.println(max_ppl);
	}
}