Resolver problemas algorítmicos: la posibilidad de reservar un hotel

La traducción del artículo fue preparada especialmente para los estudiantes del curso "Algoritmos para desarrolladores" .



Este artículo es parte de una serie sobre cómo resolver problemas algorítmicos. Según mi experiencia personal, descubrí que la mayoría de los recursos simplemente describen la solución en detalle. Lamentablemente, una explicación de la línea principal de razonamiento que permite encontrar una solución efectiva no es muy común. Por lo tanto, el objetivo de esta serie es describir el posible curso de razonamiento para resolver problemas desde cero.

---

Desafío

• Tarea: Bit de entrevista

El gerente del hotel debe procesar N pedidos de reserva para la próxima temporada. Su hotel tiene K habitaciones. La información de reserva contiene la fecha de entrada y la fecha de salida. El gerente quiere averiguar si hay suficientes habitaciones en el hotel para satisfacer la demanda.

Datos de entrada:

- El primero en ingresar a una lista con información sobre la hora de llegada
- Segundo: una lista con información sobre la hora de salida
- Tercero - K, que indica el número de habitaciones

Datos de salida:
- Un valor lógico que indica la capacidad de reservar habitaciones.
falso significa que el hotel no tiene suficientes habitaciones para N reservas
cierto significa que el hotel tiene suficientes habitaciones para N reservas

Un ejemplo:

Datos de entrada:
- registro = [1, 3, 5]
- salida = [2, 6, 10]
- K = 1

Salida: falso. El día = 5 el hotel tiene 2 huéspedes. Pero solo tenemos un número.

• Categoría: Matrices

Proceso de decisión

Esta tarea es interesante, en mi opinión, porque hay muchas formas diferentes de resolverla. Veamos las opciones.

Una estructura que almacena contadores para cada día.
La primera idea puede ser que necesitamos una estructura para almacenar el número de pedidos por día. Esta estructura puede ser una matriz con un tamaño fijo (determinado por el día máximo de salida).

Datos de entrada:
- entradas = [1, 3, 5]
- salidas = [2, 6, 10]
- k = 1

Para este ejemplo, el tamaño de la matriz será 10 (porque la última salida el día 10). Para completar esta matriz, revisamos las listas de entradas y salidas y aumentamos o disminuimos el contador del día correspondiente. Ejemplo de pseudocódigo:

int[] counts = new int[maxDepartures(departures)] for each arr in arrivals { counts[arr]++ } for each dep in departures { counts[dep]-- } 

Como resultado, obtenemos la siguiente matriz:

: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10

Una vez que la matriz está llena, solo necesita revisarla y verificar si todos los elementos no exceden k (número de habitaciones).

En el ejemplo anterior, el número máximo de habitaciones era 1. Como en el día 5 tenemos 2 reservas, devolvemos false .

La complejidad temporal de esta solución es O (n), donde n es el número de reservas, y espacial es O (m), donde m es el día máximo de salida. No está mal en teoría, pero es probable que asigne mucha memoria para una gran matriz, aunque la mayor parte no se utilizará.

Por ejemplo:

Datos de entrada:
- entradas = [1, 3, 5]
- salidas = [2, 10000, 10]
- k = 1

En este caso, se asignará una matriz de 10 mil enteros.

Veamos otras soluciones.

Almacenamiento de colección de eventos

¿Qué otras opciones hay? Veamos nuevamente lo que sucedió con la estructura anterior:

: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10

Vemos que cierta información está duplicada. Por ejemplo, entre 6 y 9 días, el número de reservas no cambia, ya que sabemos que no pasará nada durante este período de tiempo.

¿Podría ser mejor si los eventos se almacenan en su lugar? Tomemos el mismo ejemplo nuevamente:

Datos de entrada:
- entradas = [1, 3, 5]
- salidas = [2, 6, 10]
Día 1: +1 reserva
Día 2: -1 reserva
Día 3: +1 reserva
Día 6: -1 reserva
Día 5: +1 reserva
Día 10: -1 reserva

La solución es iterar sobre estos eventos para aumentar o disminuir el contador. Si en algún momento el contador es mayor que k , devolvemos false . Sin embargo, para buscar, esta colección de eventos debe ordenarse.

¿Qué estructura es mejor usar aquí? Resumamos nuestros requisitos:

• Busque para verificar si ese día ya existe
• Añadiendo un nuevo día,
• Vea la estructura para iterar sobre cada día ordenado.

¿Qué tal usar un árbol de búsqueda binario (BST)?

Cada nodo se puede representar de la siguiente manera:

 class Node { int day int count Node left Node right } 

La clasificación se realizará en el campo del day .

Veamos las consecuencias en términos de complejidad temporal:

• Busque para verificar si ese día ya existe: O (log (n)) en el caso promedio, O (n) en el peor de los casos,
• Agregar un nuevo día: O (log (n)) en el caso promedio, O (n) en el peor de los casos,
• Vea la estructura para iterar sobre cada día ordenado: O (n) usando una búsqueda en profundidad.

Como tenemos que clasificar cada elemento e insertarlo en el árbol, la complejidad del algoritmo es O (n log (n)) en el caso promedio, O (n²) en el peor de los casos.

Otra opción es usar una tabla hash y ordenar las claves después de agregar todos los eventos:

• Busque para verificar si ese día ya existe: O (1) en el caso promedio, O (n) en el peor de los casos (la probabilidad depende de la capacidad de la matriz asociativa),
• Agregar un nuevo día: O (1) en el caso promedio, O (n) en el peor de los casos,
• Vea la estructura para iterar sobre cada día ordenado: O (n log (n)) para ordenar las claves y O (n) para ordenar.

Al final, la solución tiene O (n log (n)) en el caso del medio (debido a la operación de clasificación), O (n²) en el peor de los casos. Esta solución parece tener la misma complejidad que una solución basada en árbol.

Veamos una posible implementación en Java utilizando una matriz asociativa ordenada:

 public boolean hotel(ArrayList<Integer> arrivals, ArrayList<Integer> departures, int k) { //   Map<Integer, Integer> events = new HashMap<>(); //   int n = arrivals.size(); for (int i = 0; i < n; i++) { int arrival = arrivals.get(i); int departure = departures.get(i); //      Integer current = events.get(arrival); events.put(arrival, current == null ? 1 : current + 1); //      current = events.get(departure); events.put(departure, current == null ? -1 : current - 1); } //    Map<Integer, Integer> sortedEvents = new TreeMap<>(events); int count = 0; for (Map.Entry<Integer, Integer> entry : sortedEvents.entrySet()) { count += entry.getValue(); //  count     if (count > k) { return false; } } return true; } 

Complejidad espacial constante

Si queremos optimizar nuestro algoritmo, debemos pensar si es realmente necesario almacenar todos estos eventos. ¿No podemos simplemente clasificar los datos de recopilación (entradas y salidas) y verificar el límite de reserva en el proceso?

Es posible una solución, pero para esto sería necesario simplificar los datos de entrada ordenándolos por adelantado.

Si ambas colecciones están ordenadas, simplemente podemos iterar sobre cada elemento usando dos punteros (uno para entradas y otro para salidas), y verificar las restricciones sobre la marcha.

Como puede ver, durante cada iteración aún necesitamos verificar el mínimo entre arrivals.get(indexArrival) departures.get(indexDeparture) para averiguar qué puntero necesita actualizarse.

En general, el algoritmo tiene una complejidad temporal y espacial constante O (n log (n)) debido a las operaciones de clasificación.