PROBLEM LINKSDIFFICULTYEASY PREREQUISITESGreedy PROBLEMThere is a hotel that has R rooms, numbered 0 through R1. 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, ..., R1, 0, 1, ..., K1 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 N1. 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. EXPLANATIONThe 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 ith 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 R1We can always make guest i finally stay in room i for 0 ≤ i ≤ R1 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 ≤ R1; i++: room[i] = i  inconv[i] stay_time[i] = 31415926 Phase 2. Allocating guests R through N1If the number of guests is less than or equal to R, then we are done. Else, we have to allocate guests R through N1. 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 R1. Here is how to do this. Let last_guest be the index of the last guest that finally stayed in room R1 (initially it is R1). 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 R1. We also set stay_time[i] = 31415926 and also update last_guest = i. last_guest := R1 for i := R; i ≤ N1; 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 SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 18 Feb '13, 00:05

During phase 1, If inconv[1] = 1, shouldn't we set room[1] = 0 instead of room[0] = 0?
It is fixed.