Hotel Bookings Possible

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 :

We are given an another array containing the departure dates:

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: 

#include <bits/stdc++.h> using namespace std; bool hotel(vector < int > & arrive, vector < int > & depart, int K) {   // If rooms given are zero   if (K == 0)      return false;   int N = arrive.size();   // This vector will be storing arrival dates as well as departure dates   vector < pair < int, int > > vec;   for (int i = 0; i < N; ++i) {      vec.push_back(make_pair(arrive[i], 1));      vec.push_back(make_pair(depart[i], 0));   }   // Sorting the vector   sort(vec.begin(), vec.end());   // This will be storing the current rooms occupied   int curActive = 0;   // This will be storing the maximum rooms occupied till then   int maxAns = 0;   // Traversing the vector   for (int i = 0; i < vec.size(); i++) {      // If this is a arrival date      if (vec[i].second == 1) {         curActive++;         //Taking maximum of rooms occupied till now and the rooms occupying at current         maxAns = max(maxAns, curActive);      }      // If this is a departure date      else {         curActive--;      }   }   //If rooms given are greater than or equal to the max rooms required   if (K >= maxAns) return true;   //otherwise returning false   return false; } int main() {   int days, K;   vector < int > arrive;   vector < int > depart;   cin >> days;   for (int i = 0; i < days; i++) {      int elem;      cin >> elem;      arrive.push_back(elem);   }   for (int i = 0; i < days; i++) {      int elem;      cin >> elem;      depart.push_back(elem);   }   cin >> K;   bool ans = hotel(arrive, depart, K);   cout << ans;   return 0; } You can also try this code with Online C++ Compiler Run Code

Input: 3 1 3 5 2 6 8 1 You can also try this code with Online C++ Compiler Run Code

Output : 0 You can also try this code with Online C++ Compiler Run Code

Also see,  Euclid GCD Algorithm