Una habitación para alquilar, seleccione las reservas para minimizar los días no alquilados.

Question

En primer lugar, no sé si es un problema estrictamente matemático, pero he pensado en preguntar aquí también.

Hay una habitación en alquiler en 2017 con un gran número de solicitudes de reserva. Todas las solicitudes consisten en un día de llegada y un día de salida. Ya se han recibido todas las solicitudes para el año 2017. Muchas solicitudes se sobrepasan, sin embargo, una vez que se acepta una solicitud, la habitación queda reservada para todos los días desde el día de llegada hasta el día de salida. ¿Cuál es el mejor enfoque (algoritmo) para aceptar estas solicitudes de forma que la habitación quede sin reservar el menor número de días posible en 2017?

Answer 1

En primer lugar, ordene las solicitudes de reserva por su fecha de inicio.

Ahora toma un array de $n$ entradas (en su caso $n=365$ ) y llenarlo con $0$ 's. El $i-$ El número de la matriz representa el máximo de días posibles en los que la sala estará llena, de modo que estará libre al comienzo del $i-$ día. En otras palabras, un cliente que hizo una reserva que comienza el $i-$ a día de hoy podría ser bienvenido. Para simplificar, utilizaré $a[i]$ para denotar el $i-$ de la matriz.

Ahora tome la primera solicitud (ordenada) y cuente cuántos días se quedará el huésped. Si su última fecha de estancia es $k$ y su primera es $m$ entonces en $a[k+1]$ escriba el máximo del valor actual de $a[k+1]$ y $a[m]+k+1-m$ . Y hacer lo mismo para $a[k+2], a[k+3]$ y así hasta el final de la tabla. De hecho, debido a cómo llenamos la tabla una vez $a[m]+k+1-m$ no es mayor que $a[k+i]$ podemos dejar de comprobar el resto de las entradas, ya que las entradas de las matrices están en orden creciente.

Una vez que se procesan todas las solicitudes de reserva, sólo hay que leer la última entrada del array. Ese es el máximo de días posibles que se puede utilizar la habitación.

---

Si buscas la justificación de este algoritmo, sólo tienes que observar que es muy similar a la programación dinámica.