Solving algorithmic problems: the possibility of booking a hotel
The translation of the article was prepared specifically for students of the course "Algorithms for Developers" .
This article is part of a series on how to solve algorithmic problems. Based on my personal experience, I found that most resources just describe the solution in detail. An explanation of the main line of reasoning that allows finding an effective solution, unfortunately, is not very common. Therefore, the goal of this series is to describe the possible course of reasoning for solving problems from scratch.
This task is interesting, in my opinion, in that there are many different ways to solve it. Let's look at the options.
A structure that stores counters for each day
The first idea may be that we need a structure to store the number of orders for each day. This structure can be an array with a fixed size (determined by the maximum departure day).
For this example, the size of the array will be 10 (because the last exit on day 10). To fill this array, we go through the lists of entries and exits and increase or decrease the counter of the corresponding day. Pseudo-code example:
As a result, we get the following array:
After the array is full, you just need to go through it and check if all the elements do not exceed
(number of rooms).
In the previous example, the maximum number of rooms was 1. Since on day 5 we have 2 reservations, we return
.
The time complexity of this solution is O (n), where n is the number of reservations, and spatial is O (m), where m is the maximum departure day. Not bad in theory, but it is likely to allocate a lot of memory for a large array, although most of it will not be used.
For example:
In this case, an array of 10 thousand integers will be allocated.
Let's look at other solutions.
What other options are there? Let's look again at what happened with the previous structure:
We see that some information is duplicated. For example, between 6 and 9 days the number of bookings does not change, since we know that nothing will happen during this period of time.
Could it be better if events are stored instead? Let's take the same example again:
The solution is to go through these events to increase or decrease the counter. If at some point the counter is greater than
, we return
. However, in order to iterate over, this collection of events needs to be sorted.
What structure is better to use here? Let's summarize our requirements:
How about using a binary search tree (BST)?
Each node can be represented as follows:
Sorting will be done on the
field.
Let's look at the consequences in terms of time complexity:
Since we have to sort through each element and insert it into the tree, the complexity of the algorithm is O (n log (n)) in the average case, O (nĀ²) in the worst case.
Another option is to use a hash table and sort the keys after adding all the events:
In the end, the solution has O (n log (n)) in the middle case (due to the sort operation), O (nĀ²) in the worst case. This solution seems to have the same complexity as the tree-based solution.
Let's look at a possible implementation in Java using a sorted associative array:
If we want to optimize our algorithm, we need to think about whether it is really necessary to store all these events? Can't we just iterate over the collection data (entries and exits) and check the reservation limit in the process?
A solution is possible, but for this it would be necessary to simplify the input data by sorting it in advance.
If both collections are sorted, we can simply iterate over each element using two pointers (one for entries and one for departures), and perform a check of the restrictions on the fly.
As you can see, during each iteration we still need to check the minimum between
to find out which pointer needs to be updated.
In general, the algorithm has constant temporal and spatial complexity O (n log (n)) due to sorting operations.
This article is part of a series on how to solve algorithmic problems. Based on my personal experience, I found that most resources just describe the solution in detail. An explanation of the main line of reasoning that allows finding an effective solution, unfortunately, is not very common. Therefore, the goal of this series is to describe the possible course of reasoning for solving problems from scratch.
A task
- Task: InterviewBit
The hotel manager must process N reservation orders for the next season. His hotel has K rooms. Booking information contains the check-in date and check-out date. The manager wants to find out if there are enough rooms in the hotel to satisfy the demand.
Input data:
- The first to enter a list with information about the time of arrival
- Second - a list with information about the time of departure
- Third - K, indicating the number of rooms
Output:
- A logical value that indicates the ability to book rooms
false means the hotel does not have enough rooms for N bookings
true means the hotel has enough rooms for N bookings
Example:
Input data:
- check-in = [1, 3, 5]
- departure = [2, 6, 10]
- K = 1
Output: false. On the day = 5 the hotel has 2 guests. But we only have one number.
- Category: Arrays
Decision process
This task is interesting, in my opinion, in that there are many different ways to solve it. Let's look at the options.
A structure that stores counters for each day
The first idea may be that we need a structure to store the number of orders for each day. This structure can be an array with a fixed size (determined by the maximum departure day).
Input data:
- entries = [1, 3, 5]
- departures = [2, 6, 10]
- k = 1
For this example, the size of the array will be 10 (because the last exit on day 10). To fill this array, we go through the lists of entries and exits and increase or decrease the counter of the corresponding day. Pseudo-code example:
int[] counts = new int[maxDepartures(departures)] for each arr in arrivals { counts[arr]++ } for each dep in departures { counts[dep]-- }
As a result, we get the following array:
: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10
After the array is full, you just need to go through it and check if all the elements do not exceed
k
(number of rooms).
In the previous example, the maximum number of rooms was 1. Since on day 5 we have 2 reservations, we return
false
.
The time complexity of this solution is O (n), where n is the number of reservations, and spatial is O (m), where m is the maximum departure day. Not bad in theory, but it is likely to allocate a lot of memory for a large array, although most of it will not be used.
For example:
Input data:
- entries = [1, 3, 5]
- departures = [2, 10000, 10]
- k = 1
In this case, an array of 10 thousand integers will be allocated.
Let's look at other solutions.
Event Collection Storage
What other options are there? Let's look again at what happened with the previous structure:
: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10
We see that some information is duplicated. For example, between 6 and 9 days the number of bookings does not change, since we know that nothing will happen during this period of time.
Could it be better if events are stored instead? Let's take the same example again:
Input data:
- entries = [1, 3, 5]
- departures = [2, 6, 10]
Day 1: +1 booking
Day 2: -1 booking
Day 3: +1 booking
Day 6: -1 booking
Day 5: +1 booking
Day 10: -1 booking
The solution is to go through these events to increase or decrease the counter. If at some point the counter is greater than
k
, we return
false
. However, in order to iterate over, this collection of events needs to be sorted.
What structure is better to use here? Let's summarize our requirements:
- Search to check if a day already exists
- Adding a new day,
- View structure to iterate over each sorted day.
How about using a binary search tree (BST)?
Each node can be represented as follows:
class Node { int day int count Node left Node right }
Sorting will be done on the
day
field.
Let's look at the consequences in terms of time complexity:
- Search to check if such a day already exists: O (log (n)) in the average case, O (n) in the worst case,
- Adding a new day: O (log (n)) in the average case, O (n) in the worst case,
- View the structure for iterating over each sorted day: O (n) using a depth search.
Since we have to sort through each element and insert it into the tree, the complexity of the algorithm is O (n log (n)) in the average case, O (nĀ²) in the worst case.
Another option is to use a hash table and sort the keys after adding all the events:
- Search to check if such a day already exists: O (1) in the average case, O (n) in the worst case (the probability depends on the capacity of the associative array),
- Adding a new day: O (1) in the average case, O (n) in the worst case,
- View the structure for iterating over each sorted day: O (n log (n)) for sorting keys and O (n) for sorting.
In the end, the solution has O (n log (n)) in the middle case (due to the sort operation), O (nĀ²) in the worst case. This solution seems to have the same complexity as the tree-based solution.
Let's look at a possible implementation in Java using a sorted associative array:
public boolean hotel(ArrayList<Integer> arrivals, ArrayList<Integer> departures, int k) { // Map<Integer, Integer> events = new HashMap<>(); // int n = arrivals.size(); for (int i = 0; i < n; i++) { int arrival = arrivals.get(i); int departure = departures.get(i); // Integer current = events.get(arrival); events.put(arrival, current == null ? 1 : current + 1); // current = events.get(departure); events.put(departure, current == null ? -1 : current - 1); } // Map<Integer, Integer> sortedEvents = new TreeMap<>(events); int count = 0; for (Map.Entry<Integer, Integer> entry : sortedEvents.entrySet()) { count += entry.getValue(); // count if (count > k) { return false; } } return true; }
Constant spatial complexity
If we want to optimize our algorithm, we need to think about whether it is really necessary to store all these events? Can't we just iterate over the collection data (entries and exits) and check the reservation limit in the process?
A solution is possible, but for this it would be necessary to simplify the input data by sorting it in advance.
If both collections are sorted, we can simply iterate over each element using two pointers (one for entries and one for departures), and perform a check of the restrictions on the fly.
As you can see, during each iteration we still need to check the minimum between
arrivals.get(indexArrival) departures.get(indexDeparture)
to find out which pointer needs to be updated.
In general, the algorithm has constant temporal and spatial complexity O (n log (n)) due to sorting operations.
All Articles