Maximum Occupancy Revisited
We revisit problem Maximum Occupancy and give a simpler solution. You can find our previous solution here.
Problem Statement
You work for a chain of hotels. The central management asks you to make a report that includes some metrics for each month and hotel. The report must include the maximum occupancy. Given that the only data you have that is related to occupancy is a list of room reservations for each month and hotel, how do you obtain the maximum occupancy?
For a given hotel and day, occupancy is the number of rooms that are occupied on that day. We consider that a room is occupied when the reservation is paid. After a room is paid, we do not make the room available even if guests do not show up on the first date of their reservation.
Each reservation that you have is fully paid. Each reservation consists of a check-in date and a check-out date. Each reservation corresponds to a single room. For that reason, two overlapping reservations correspond to different rooms. Given a reservation, the corresponding room is occupied on all dates of the reservation except the check-out date.
Consider the following example. Suppose that on February 2017 there were only 5 reservations for our hotel in Cancun.
The maximum occupancy is 3 and it happened on February 5 and 6.
Input.
The input file consists of one or more cases. Each case begins with a
positive number n
on a line of its own. Following n
, there are
n
reservations corresponding to the case, each on a separate line.
Each reservation consists of two numbers separated by one or more
spaces. The first number of a given reservation corresponds to the
day of the month where a check-in happened. The second number
corresponds to the check-out day. No reservation crosses the
boundaries of any month. The input file is terminated by an EOF
character. Consider the following example.
Output. The output file consists of an output line for each case. Each output line consists of a single integer, the maximum occupancy for the case. For example, the following output corresponds to the previous example input.
Approach
We illustrate our approach by example. Consider the following timeline of the reservations given by the example in the problem statement.
We compute the occupancy on each day in the following way. We start
with an occupancy of zero. Imagine that we sweep a line over the
diagram from left to right. Each time we step over a day, we
calculate the occupancy on the day by adding the delta occupancy for
the day. The delta occupancy for the a given day is the difference
between the count of i
’s and the count of o
’s for that day.
Consider the occupancy for each day in the example.
The result for the example is 3, which is the maximum among the occupancies in the previous diagram.
Ruby Implementation
We implement our approach in three steps. We compute the delta occupancy for each day, then the occupancy for each day, and finally the occupancy for all the reservations. Given that only days that have a check-in or check-out may have an effect on occupancy, we compute occupancies only for those.
We compute the deltas by means of a dictionary in the following way.
We take as input a list of reservations consisting of a pair of
integers day_in, day_out
. For each reservation, we increase the
delta for day_in
and decrease the delta for day_out
. We output a
list of deltas sorted by day. We implement the computation of deltas
in the following method sorted_deltas
. The run time of
the implementation is dominated by the sorting and belongs to class
$@O(r\,\text{log}(r))@$, where $@r@$ is the count of reservations.
We compute each occupancy by adding the corresponding delta to the
previous occupancy. We start with occupancy zero. We implement the
computation of occupancies in the following method occupancies
. The
run time belongs to class $@O(d)$@, where $@d@$ is the count of
deltas.
Finally, the occupancy for all the reservations is the maximum among the occupancies for each day.
The following is our Ruby implementation of the approach. The run
time of the implementation is bounded by the call to sorted_deltas
and belongs to class $@O(r\,\text{log}(r))@$, where $@r@$ is the count of
reservations.