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 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. 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.

# Solution

Our proposed solution belongs to complexity class O(n log n).

Consider the following timeline of the reservations given by the example in the problem statement.

Imagine that we sweep a line over the diagram from left to right. We start with an occupancy of zero and every time we step over at least one i or o, we add the number of i’s and subtract the number of o’s. After doing all additions and subtractions, we obtain the occupancy for the corresponding day of the month. We annotate the current occupancy below the day of the month, like so.

The result is the maximum amongst the annotated occupancies.

The sweeping of the line corresponds to considering check-ins and check-outs in chronological order. We do not need to consider dates that do not have a corresponding check-in or check-out (i.e. days 2, 4, 6, and everything after 11). To do that, sort the check-ins and check-outs and then consider each by taking every time the most recent check-in or check-out first. Consider the following Ruby procedure.

For the example input, the previous procedure prints the following.

Given the procedure for sweeping the line, compute the occupancy every time the date changes, like so.

For the example input, the previous procedure prints the following.

Given the procedure for computing occupancies, select the maximum like so.

Given the example input, the return value for the previous procedure is 3.

# Want to read more?

I love to explain and answer questions on programming problems. I publish a new programming problem and its solution every month. Did I mention that I love to answer questions?

If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.