PROBLEM LINKS
DIFFICULTY
EASY
PREREQUISITES
Greedy
PROBLEM
There is a hotel that has R rooms, numbered 0 through R-1. The hotel has this following scheme of allocating rooms to guests. If a guest prefers room K, then the hotel manager checks rooms in order K, K+1, …, R-1, 0, 1, …, K-1 and allocates the guest in the first free room in this list or report the guest that all rooms are occupied. The number of occupied rooms that are checked is called the inconvenience of the guest.
There were N guests that came to the hotel, numbered 0 through N-1. For each guest i, we know his time of visit (time[i]) and his inconvenience (inconv[i]). However, we lose the information of his preferred room and his stay time.
Determine the preferred room (room[i]) and the stay time (stay_time[i]) of each guest i such that all information are consistent.
EXPLANATION
The problem statement says that an answer is always guaranteed to exist. We will show that an answer exists if and only if 0 ≤ inconv[i] ≤ min(i, R) for all 0 ≤ i < N. We will prove the implication in both directions as follows.
First, the condition is necessary because when the i-th guest comes, the hotel can only have at most i rooms occupied already, so inconv[i] cannot be larger than i. Of course, inconv[i] cannot be larger than R as well because the hotel only has R rooms.
Second, the condition is sufficient because we can always construct a consistent answer as follows. We will separate the answer into two phases.
Phase 1. Allocating guests 0 through R-1
We can always make guest i finally stay in room i for 0 ≤ i ≤ R-1 as follows. First, guest 0 will have zero inconvenience, so we can set room[0] = 0. Next, guest 1 can have 0 or 1 inconvenience. If inconv[1] = 0, then we can set room[1] = 1. If inconv[1] = 1, then we can set room[1] = 0 so that when the manager checks room 0, the room has already been occupied and finally he is allocated to room 1.
In general, we can set room[i] = i - inconv[i]. For this to work, all previous guests must still stay when we process guest i, so we can set stay_time[i] = 31415926 (i.e. the maximum allowed duration).
for i := 0; i ≤ R-1; i++:
room[i] = i - inconv[i]
stay_time[i] = 31415926
Phase 2. Allocating guests R through N-1
If the number of guests is less than or equal to R, then we are done. Else, we have to allocate guests R through N-1. Here we can always allocate the remaining guests as follows. Note that now all rooms are occupied with the maximum possible stay times. There are two possible conditions for guest i, i ≥ R.
inconv[i] = R
Since all R rooms are occupied, we can set room[i] to any room as guest i’s inconvenience will be R. We can simply set room[i] = 0. We can also set stay_time[i] to any value, so let’s set stay_time[i] = 31415926.
inconv[i] < R
We can always make guest i finally stay in room R-1. Here is how to do this. Let last_guest be the index of the last guest that finally stayed in room R-1 (initially it is R-1). Then, we can set room[i] = R - 1 - inconv[i] and stay_time[last_guest] = time[i] - time[last_guest]. In this way, guest last_guest will leave at the same time guest i arrives, so we can still have available room for guest i at room R-1. We also set stay_time[i] = 31415926 and also update last_guest = i.
last_guest := R-1
for i := R; i ≤ N-1; i++:
if inconv[i] == R:
room[i] := 0
else:
room[i] = R - 1 - inconv[i]
stay_time[last_guest] := time[i] - time[last_guest]
last_guest := i
stay_time[i] := 31415926
In conclusion, we have a very simple O(N) solutions that always allocates all guests consistently.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.