Description
Goal
The goal of this assignment is to familiarize the students with creating dynamic memory in the C
programming language.
Problem
You work of a large chain of hotels. Each hotel allows customers to reserve rooms for a fixed
amount of time. Where the big bucks come in is when the hotel rents out its ballroom. Each
person knows the exact ballroom they wish to reserve and the exact time in which they will need
the room. Your company wishes to treat all of its customers fairly, by giving priority to the first
customer to ask for the room.
Write a program that takes in the number of ballrooms, and process a series of updates and
queries regarding the states of the ballrooms.
Input Specification
Note that within the input specification the quotes around words are for clarity purposes only and
will not be included in the actual input. Each name will contain between 1 and 100 lower case
and/or upper case Latin characters.
The first line of input begin with a positive integer, n (n ≤ 100,000), which represents the
number of ballrooms in your hotel. Each ballroom has an identification number between 1 and n
inclusive.
Each line following the first will either begin with the word “RENT”, “WHO”, or “END”. If the
word “END” begins a line, your program should stop processing input and exit eventually.
If the word “RENT” begins a line the word will be followed by a space and three space separated
integers, i, s, e (0 ≤ s < e ≤ 1,000,000), which represents a valid identification number for the
room requested, the start time when the room is rented, the time at which the renters will have
left, respectively. Following this will be space followed by a name (without whitespace) for the
reservation. If someone already occupies that room during the requested time, then the current
rent request will be denied.
If the word “WHO” begins a line then the word will be followed by a space and two space
separated integers, i and t (0 ≤ t ≤ 1,000,000), which represents a valid identification number for
the queried room, and the time at which the query takes place, respectively. Your program will
determine if the given room is occupied from time t to t + 1.
Input will always contain an “END” command.
Output Specification
For each “RENT” request output a 1 if the request was successful and a 0 otherwise. This integer
should be on a line by itself.
For each “WHO” request output a 0 if the room is unoccupied, otherwise output the name of the
reservation. The result should be on a line by itself.
Input Output Example
Input Output
6
RENT 1 0 10 John
RENT 1 10 20 Jeff
WHO 1 10
WHO 1 9
WHO 2 10
RENT 2 0 20 Jacob
WHO 2 10
END
1
1
Jeff
John
0
1
Jacob
2
RENT 1 0 100 Alice
RENT 1 0 10 Bob
RENT 1 20 30 Carol
RENT 1 40 50 David
RENT 1 60 70 Erin
WHO 1 100
WHO 1 0
RENT 2 0 10 Fred
WHO 2 9
WHO 1 10
END
1
0
0
0
0
0
Alice
1
Fred
Alice
Explanation
Case 1
The first line says there are 6 rooms
The rooms are initially unoccupied. When John tries to rent the room he is successful. [ 1 is
outputted ]
Jeff tries to rent the first room starting at time 10. John should already be gone by then, so the
hotel allows Jeff to reserve the room (hopefully John does not run late). [ 1 is outputted ]
We then question who is allowed to occupy the first room between 10 and 11. The answer is Jeff.
[ Jeff is outputted ]
The question is then who occupies the first room between 9 and 10. The answer is John this time.
[ John is outputted ]
The third question is who occupies the second room between 10 and 11. However, no one has
reserved the second room yet. So the answer is no one. [ 0 is outputted ]
Jacob tries to rent the second room starting at 0 and ending at 20. He is successful. [ 1 is
outputted ]
Finally we question who occupies the second room from 10 to 11. This time Jacob has reserved
the room, and Jacob actually has the room at said time. [ Jacob is outputted ]
Case2
The first line of input indicates there is only 2 rooms.
Alice rents the first room from 0 to 100. [ 1 is outputted ]
Bob fails to rent the first room [ 0 is outputted ]
Carol fails to rent the first room [ 0 is outputted ]
David fails to rent the first room [ 0 is outputted ]
Erin fails to rent the first room [ 0 is outputted ]
No one has the first room from time 100 to 101 [ 0 is outputted ]
Alice has the first room from time 0 to 1 [ Alice is outputted ]
Fred successfully rents room 2 from time 0 to time 10 [ 1 is outputted ]
Fred has the second room from time 9 to 10 [ Fred is outputted ]
Alice has the first room from time 10 to time 11 [ Alice is outputted ]
Grading Information
Good comments, whitespace, and variable names – 15 points
Reading from and writing to standard input/output – 5 points
No extraneous output – 10 points
Use an array list to represent each room’s occupants – 10 points
Use an array to store pointers to the rooms’ array lists – 10 points
Your program will be tested on 10 test cases – 5 points each
Most likely 0 points will be awarded to programs that do not compile using “gcc –std=gnu11”.
Solutions without dynamic memory will receive a maximum of 50 points