Introduction.
In this blog, we will discuss the most frequently asked question that is Hotel Bookings Possible. But before moving towards the solution, we have to understand the problem of hotel bookings possible first. So the problem goes like this:
Suppose you are a Hotel Manager and you have to process N advance Bookings for the next season. You have C rooms in your hotel. You are given the arrival and departure dates of the bookings. You have to find out whether there are enough rooms in the hotel so that you can accommodate all the bookings.
Return true if these bookings are possible; otherwise, return false
Let’s take an example for it:
Here you are given an array containing the arrival dates :
1 
3 
5 
We are given an another array containing the departure dates:
2 
6 
8 
Here for this example let’s consider number of rooms given be 1.Here you can see that:
suppose a room is booked on date 1 then it will be occupied till date 2.
And suppose you booked that room again on date 3 then it will be occupied till date 6
Now the room can not be occupied for the booking on date 5 because the room is already occupied till 6 and we are given one room in the hotel. So now you can see that it is not possible to accommodate all the bookings.So you should print false i.e 0 as your output.
As wee have understood the question. Now is the time to move towards its solution. Let’s discuss the solution in steps for better understanding.
Step 1. Take a vector of pair class. In this vector, we will be storing the arrival dates and the departure dates.
Step 2. Now you must be thinking about why we need vectors that can store a pair of integers!! So let me answer this question. Actually, I want something that can help me identify whether this integer is from arrival dates or departure dates. So I will be storing 1 with arrival dates and will be keeping 0 with departure dates.
Step 3. Now sort this vector.
Step 4. Now start iterating this vector. Check if this is an arrival date or departure date. Now how will you identify? Yes, you guessed it right! We have mentioned integer 1 for arrival and 0 for departure in our vector of pairs. So with that, we can easily check if it’s arrival date or departure date
If this is an arrival date, then increase no of rooms required by 1.
If this is a departure date, then decrease the number of rooms required by 1.
Step 5. Now the important thing to pay attention here is that we have to maintain the maximum number of rooms required while traversing the vector. At last, check that rooms given in input are greater than or equal to this maximum maintained answer. If yes, then print true else, print false.
So, I have discussed all the steps of the solution. Now please try coding it out on your own only then you will be able to excel in coding.
Did you try coding it? Great, Now let’s see our way of writing code for it!
C++ Solution:



Also see, Euclid GCD Algorithm