Hotel Bookings Possible

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".

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

• 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

#include <bits/stdc++.h>
using namespace std;

bool checkBookings(int arrival[], int departure[], int n, int k)
{
	vector<pair<int, int> > temp;

	// Create a temp vector common to both arrivals and departures
    // Arrival is denoted by 1 and departure by 0
	for (int i = 0; i < n; i++) {
		temp.push_back(make_pair(arrival[i], 1));
		temp.push_back(make_pair(departure[i], 0));
	}

	// Sort the temp booking vector
	sort(temp.begin(), temp.end());

	int curr_booking = 0, max_bookings = 0;

	for (int i = 0; i < temp.size(); i++) {

		// If new booking arrives, increment current_booking count and update max_bookings 
		if (temp[i].second == 1) {
			curr_booking++;
			max_bookings = 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;

}

int main()
{
	int arrival[] = { 2, 4, 6 };
	int departure[] = { 3, 7, 9 };
	int n = sizeof(arrival) / sizeof(arrival[0]);
	int k = 1;
	cout << (checkBookings(arrival, departure, n, k)? "Yes\n": "No\n");
	return 0;
}

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; 
	} 
	}); 
} 
} 

def checkBookings(arrival, departure, n, k): 

	temp = [] 

	# Create a temp array common to both arrivals and departures
	# Arrival is denoted by 1 and departure by 0
	for i in range(0, n): 
		temp.append((arrival[i], 1)) 
		temp.append((departure[i], 0)) 

	# Sort the temp booking array 
	temp.sort() 
	curr_booking, max_bookings = 0, 0

	for i in range(0, len(temp)): 

		# If new booking arrives, increment current_booking count and update max_bookings 
		if temp[i][1] == 1: 
			curr_booking += 1
			max_bookings = max(max_bookings, curr_booking) 

		# If a guest departs, decrement current_booking count
		else:
			curr_booking -= 1

	# 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
arrival = [2,4,6] 
departure = [3,7,9]
n = len(arrival) 
if checkBookings(arrival, departure, n, 1):
	print("Yes")
else:
	print("No")

Output:

Complexity Analysis

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.