A hotel manager has to process N advance bookings of rooms for the next season. His hotel has K 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).
Input:
First list for arrival time of booking.
Second list for departure time of booking.
Third is K which denotes count of rooms.
Returns:
true if there are enough rooms for N booking
false if there are not enough rooms for N booking
My approach:
Heapsort arrive list, applying same changes to depart to maintain index relationship. A TreeSet is used to track next checkout time. For each iteration: a guest is checked in and checkout time is added to TreeSet. If a checkout has occurred, a guest is removed and next checkout is polled from TreeSet. If overbooking ever occurs, false is returned.
My solution works on NetBeans but fails when I run it through the website. Any help will be very much appreciated.
Original question: https://www.interviewbit.com/problems/hotel-bookings-possible/
public boolean hotel(ArrayList<Integer> arrive, ArrayList<Integer> depart, int K) {
TreeSet<Integer> ts = new TreeSet<>(); // stores and polls checkout times
sort(arrive, depart);
int in = 0; // current number of guests
int out = Integer.MAX_VALUE; // next checkout time
for (int i = 0; i < arrive.size(); i++) {
in++; // check in
if (out <= arrive.get(i)) { // check out
in--;
out = ts.pollFirst(); // poll next checkout time
}
if (in > K) { // guests exceed room
return false;
}
// new checkout time is earlier than current
// no need to put it into ts just to take it out
if (depart.get(i) < out) {
ts.add(out); // add current checkout to ts for future use
out = depart.get(i);
} else {
ts.add(depart.get(i));
}
}
return true;
}
// heapsort that keeps arrive:depart index in sync
public void sort(ArrayList<Integer> arrive, ArrayList<Integer> depart) {
int n = arrive.size();
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arrive, depart, n, i);
}
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
int temp = arrive.get(0);
arrive.set(0, arrive.get(i));
arrive.set(i, temp);
// maintain arrive:depart relationship
int tempD = depart.get(0);
depart.set(0, depart.get(i));
depart.set(i, tempD);
// call max heapify on the reduced heap
heapify(arrive, depart, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(ArrayList<Integer> arrive, ArrayList<Integer> depart, int n, int i) {
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arrive.get(l) > arrive.get(largest) ) {
largest = l;
}
// If right child is larger than largest so far
if (r < n && arrive.get(r) > arrive.get(largest)) {
largest = r;
}
// If largest is not root
if (largest != i) {
int swap = arrive.get(i);
arrive.set(i, arrive.get(largest));
arrive.set(largest, swap);
// maintain arrive:depart relationship
int swapD = depart.get(i);
depart.set(i, depart.get(largest));
depart.set(largest, swapD);
// Recursively heapify the affected sub-tree
heapify(arrive, depart, n, largest);
}
}
// used to print heapsort results
public void printSort(ArrayList<Integer> arrive, ArrayList<Integer> depart){
sort(arrive, depart);
for (int i = 0; i < arrive.size(); i++) {
System.out.println(arrive.get(i) + " " + depart.get(i));
}
}
// problem test scenario
HotelBookingsPossible hbp = new HotelBookingsPossible();
ArrayList<Integer> arrive2 = new ArrayList<>(Arrays.asList(
41, 10, 12, 30, 0, 17, 38, 36, 45, 2, 33, 36, 39, 25, 22, 5, 41, 24, 12, 33, 19, 30, 25, 12, 36, 8));
ArrayList<Integer> depart2 = new ArrayList<>(Arrays.asList(
47, 20, 15, 65, 35, 51, 38, 36, 94, 30, 50, 38, 67, 64, 67, 24, 62, 38, 18, 59, 20, 74, 33, 43, 56, 32));
hbp.printSort(arrive2, depart2);
System.out.println(hbp.hotel(arrive2, depart2, 12)); //true
replaced TreeSet with TreeMap since duplicate checkout times were lost.
public boolean hotel(ArrayList<Integer> arrive, ArrayList<Integer> depart, int K) {
TreeMap<Integer, Integer> ts = new TreeMap<>(); // stores and polls checkout times
sort(arrive, depart);
int in = 0; // current number of guests
int out = Integer.MAX_VALUE; // next checkout time
for (int i = 0; i < arrive.size(); i++) {
in++; // check in
// new checkout time is earlier than current
// no need to put it into ts just to take it out
if (depart.get(i) < out) {
// add current checkout to ts for future use
ts.compute(out, (key, value) -> {
if (value == null) {
return 1;
} else {
return value + 1;
}
});
out = depart.get(i);
} else {
ts.compute(depart.get(i), (key, value) -> {
if (value == null) {
return 1;
} else {
return value + 1;
}
});
}
if (out <= arrive.get(i)) { // check out
in--;
// poll next checkout time
out = ts.firstKey();
if (ts.get(out) == 1) {
ts.remove(out);
} else {
ts.compute(out, (key, value) -> {
return value - 1;
});
}
}
if (in > K) { // guests exceed room
return false;
}
}
return true;
}