Hotel Bookings Possible

Deeksha
Last Updated: May 13, 2022

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: 

#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;
}
Input:
3
1 3 5 
2 6 8
1

 

Output : 0

 

Complexity Analysis: 

Time Complexity: O(NLogN) where ‘N’ refers to the size of the input array. We have done sorting here, so this adds logN time complexity and one traversal of this vector adds up to (NLogN) time complexity.

 

Space Complexity: O(N) where ‘N’ refers to the size of the input array. We are using a vector that is adding to this space complexity.

Frequently Asked Questions: 

Ques 1 . Can I do the problem of hotel bookings possible in less than O(NLogN) time complexity? 

Ans 1. No, You can’t because to solve this question you have to sort it to get an idea of which date is arriving early, departure one or arrival one. And then, you need to traverse the vector at least once.

 

Ques 2. Can I do this question with arrays instead of using vectors?

Ans 2. Yes! You can. You can use arrays to store your data for this question. You can also do this question by making two arrays instead of a single vector of pair class.

Key Takeaways: 

In this article, we discussed the problem of hotel bookings possible, which is a frequently asked question in organizations like Microsoft and Goldman Sachs. So do try coding it out on your own now because who knows! This could be the question you are going to face in the interview for your dream company. Remember to do complexity analysis of your code as we did in this blog because you are expected to know about the complexity of your solution in your interviews. If you want to practice more awesome questions like this, then do visit this amazing platform CodeStudio.

 

If you feel that this blog has helped you, please do share this blog with your friends because this is how Knowledge grows. Happy Coding!

 

By: Deeksha Rajput

Was this article helpful ?
0 upvotes