Posts Hotel Bookings Possible (InterviewBit)
Post
Cancel

Hotel Bookings Possible (InterviewBit)

Problem Description

A hotel manager has to process N advance bookings of rooms for the next season. His hotel has C rooms. Bookings contain an arrival date and a departure date. He wants to find out whether there are enough rooms in the hotel to satisfy the demand. Write a program that solves this problem in time O(N log N) . Note- If we have arrival and departure on the same date then arrival must be served before the departure.

InterviewBit

Solution

This problem can we solved in the same way as Meeting Rooms II.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {

    public boolean hotel(ArrayList<Integer> arrive, ArrayList<Integer> depart, int K) {

        int n = arrive.size();

        // Sort arrival and departure lists separately
        Collections.sort(arrive);
        Collections.sort(depart);

        int rooms = 0;

        int i = 0; // Pointer for arrival list
        int j = 0; // Pointer for departure list

        while (i < n) {

            // If the current arrival is before or equal to the current departure
            // That means, we will need one more room
            if (arrive.get(i) <= depart.get(j)) {

                rooms++; // Increment rooms as a new guest arrives
                i++;     // Move to the next arrival

            // Otherwise, there is one meeting which ended, we one room is free
            } else {

                j++;     // Move to the next departure, a guest has left
                rooms--; // Decrement rooms as a guest departs

            }

            // Check if the number of rooms in use exceeds the available rooms
            if (rooms > K)
                return false; // Not enough rooms available

        }

        // If the loop completes without returning false, there are enough rooms
        return true;

    }
}
This post is licensed under CC BY 4.0 by the author.