6
$\begingroup$

First off I do not know if it is strictly a mathematical problem, but I figured I would ask here aswell.

There is one room for rent in 2017 with a big number of reservation requests. All requests consist of an arrival day and a departure day. All requests for the year 2017 have already been received. Many requests overleap, however once a request is accepted, the room is reserved for all days from arrival day to departure day. What is the best approach (algorithm) to accept such requests that the room remains unreserved for as few days in 2017 as possible?

|cite|improve this question
$\endgroup$
3
$\begingroup$

First sort the reservation request by their starting date.

Now take an array of $n$ entries (in your case $n=365$) and fill it with $0$'s. The $i-$th number in the array represent the maximum possible days the room will be full, such that it will be free at the start of the $i-$th day. In other words a customer that made a reservation that starts on the $i-$th day might be welcomed. For simplicity I will use $a[i]$ to denote the $i-$th entry of the array.

Now take the first request (sorted) and count how many days the guest will stay. If his last date of stay is $k$ and his first is $m$ then in $a[k+1]$ write the maximum of the current value of $a[k+1]$ and $a[m]+k+1-m$. And do the same for $a[k+2], a[k+3]$ and so on till the end of the table. In fact because of how we fill the table once $a[m]+k+1-m$ is not greater than $a[k+i]$ we can stop checking for the rest of the entries, as the entries in the arrays are in increasing order.

Once you process all the reservation request, just read the last entry in the array. That's the maximum possible days that the room can be used.

If you search for justification of this algorithm, just notice that it's very similar to dynamic programming.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The method is not completely see through to me. I fear it will not be able to give information about the actual guest list with the maximum possible days rented. Is it true? $\endgroup$ – B.Swan Jan 3 '17 at 23:10
  • 1
    $\begingroup$ @B.Schnebbler I slightly misunderstood the question then, as I thought that the only important number is the maximum days that the room can be full. Anyway to address the actual problem, you can keep a second array, which will keep track of the optimal sequence of guest up to the i-th day. So when you do the updates in the algorithm, you just take the entry of the m-th entry in the new array and you just append the label given to the guest in question to it. Then make this the entry in the new array in the (k+1)-th day and so on, depending on where we made updates in the first array $\endgroup$ – Stefan4024 Jan 3 '17 at 23:17
  • $\begingroup$ If I understand correctly, you always accept the request with the earliest arrival day. But let us assume that all guests but two arrive after the first month. The first guest arrives the first day, stays for two days. The second guest arrives the second day, stays for seven days. It would be optimal to accept the second guest. But doesn't the algorithm accept the first guest? $\endgroup$ – B.Swan Jan 4 '17 at 17:23
  • 1
    $\begingroup$ @B.Schnebbler I'm afraid you misunderstood something. For the sake of simplicity let assume only those two guests made a reservation. Now assume we accept the first guest. According to the algorithm $a[3] = \max(a[1]+2,a[3]) = \max(2,0) = 2$. And the same for $a[4], a[5]...$. Now assume that the second guest is accepted. That's only possible if the room is free on the second day. $a[2]$ tells us the maximum number of days the room can be full, but it's empty on the second day. $\endgroup$ – Stefan4024 Jan 4 '17 at 17:33
  • 1
    $\begingroup$ @B.Schnebbler So now as he stays for $7$ days update the values of the arrays. $a[9] = \max(a[2]+7,a[9]) = \max(7,2) = 7$ and the same for $a[10], a[11]...$. As we've processed all the guest, take a look at the last entry of the table. Let it be $a[30]$ and it will have value $7$, which indeed is the maximum possible days for the room to be full. $\endgroup$ – Stefan4024 Jan 4 '17 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.