Many times, interview questions are based on real world applications and today we shall be discussing one such problems known as the "Hotel Bookings Possible" problem.

## Problem Description

In this problem, you are working as a hotel manager who has to process **N **advance bookings of rooms for the next season. The hotel consists of **K** rooms in total. Each booking has an arrival date and a departure date. Your task is to find out to whether there are enough rooms in the hotel to satisfy the demand, i.e. find __if there are enough rooms for N bookings.__ All the **N** meetings are given in the form of 2 arrays with arrival and departure time along with the number of rooms in the hotel **K**, and you must print "**Yes**" if the rooms can be booked otherwise print "**No**".

Example:

Input :

Arrival : [2 4 6]

Departure : [3 7 9]

K = 1

Output: No

Atleast 2 rooms are required because 2nd and 3rd bookings overlap.

Input :

Arrival : [1 2 3]

Departure: [2 3 4]

K = 1

Output: Yes

No meetings overlap and all bookings can be processed.

## Approach

The approach here is quite simple, we assign a value of 1 to the arrival array elements and 0 to the departure array elements. Then we combine them in a temporary array and sort this array. From this sorted temp array, we traverse the elements one by one and increment current booking if it is an arrival element and decrement if it is a departure element. At every step we maintain the maximum value of the current booking in another variable. At last we check whether the maximum bookings is greater than K or not. If maximum bookings are greater, this means that more than **K **rooms are required and we return **False**, otherwise, all the bookings can be processed and we return **True**.

## Pseudocode

checkBookings(arrival, departure, n, k)

Initialize temporary array- temp := [2*n]

for i in 0 to n

Add pair (arrival[i], 1) to temp - temp.Add((arrival[i], 1))

Add pair (departure[i], 1) to temp - temp.Add((arrival[i], 1))

temp.Sort()

Initialize: curr_booking := 0, max_bookings := 0

for i in 0 to temp.Length

if temp[i][1] = 1, then

curr_booking = curr_booking + 1

max_bookings = Maximum(max_bookings, curr_booking)

else

curr_booking = curr_booking - 1

if max_bookings > k, then

return False

else

return True

- In the above pseudocode, the function
`checkBookings()`

, we firstly store arrival and departure times in a temporary array with an additional marker to indicate whether the time is arrival or departure. Here`1`

denotes arrival and`0`

denotes departure. Now we sort this array of combined arrival and departure values in ascending order. - We maintain two variables
`curr_booking`

and`max_bookings`

to store the current booking arrival and the maximum bookings arrived in a particular instant. Then we run a loop through the`temp`

array and if we encounter an**arrival pair**i.e. value 1, we increment the`curr_booking`

by one and store maximum of`curr_booking`

and`max_bookings`

in variable`max_bookings`

. - If a departure pair is encountered, we decrement the
`curr_booking`

count. After the loop we check if the value of`max_bookings`

is greater than`k`

and, if it is greater then we return**False**since the bookings are more than the limit of the hotel otherwise we can process these**N**bookings and we return**True**.

## Code

- C/C++
- Java
- Python

```
import java.io.*;
import java.util.*;
class CodesDope
{
static boolean checkBookings(int arrival[], int departure[], int n, int k)
{
Pair temp[] = new Pair[2*n];
// Create a temp array common to both arrivals and departures
// Arrival is denoted by 1 and departure by 0
int j = 0;
for (int i = 0; i < n; i++)
{
temp[i + j] = new Pair(arrival[i], 1);
temp[i + j + 1] = new Pair(departure[i], 0);
j++;
}
// Sort the temp booking array using comparator
Compare obj = new Compare();
obj.compare(temp, 2 * n);
int curr_booking = 0, max_bookings = 0;
for (int i = 0; i < 2 * n; i++)
{
// If new booking arrives, increment current_booking count and update max_bookings
if (temp[i].y == 1)
{
curr_booking++;
max_bookings = Math.max(max_bookings, curr_booking);
}
// If a guest departs, decrement current_booking count
else
curr_booking--;
}
// If max_bookings at any instant were more than the available rooms,
// return False else return True
if(max_bookings > k)
return false;
else
return true;
}
// Driver code
public static void main(String[] args)
{
int arrival[] = { 2, 3, 4 };
int departure[] = { 3, 7, 9 };
int n = arrival.length;
int k = 1;
System.out.println(checkBookings(arrival, departure, n, k) ? "Yes" : "No");
}
}
// Pair class to form pairs of arrivals and departures
class Pair {
int x;
int y;
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}
// User defined comparator class
class Compare {
static void compare(Pair arr[], int n)
{
// Comparator to sort the pair according to second element
Arrays.sort(arr, new Comparator<Pair>() {
@Override public int compare(Pair p1, Pair p2)
{
return p1.x - p2.x;
}
});
}
}
```

Output:

No

## Complexity Analysis

Method | Time Complexity | Space Complexity |
---|---|---|

checkBookings() | O(NlogN) | O(N) |

In the above algorithm, we first sort the entire temp array and then check for every booking one by one. The sorting takes O(NlogN) time and then we traverse all elements in temporary array in O(N) complexity. This makes the total time complexity as **O(NlogN)**. The extra temporary array is of size 2*N which results in a space complexity of **O(N)**.

In this way we have seen the approach to solve the "**Hotel Bookings Possible**" problem.