Менеджер отеля должен обработать N предварительных бронирований номеров на следующий сезон. В его отеле K номеров. Бронирование содержит дату прибытия и дату отъезда. Он хочет узнать, достаточно ли в гостинице номеров, чтобы удовлетворить спрос. Напишите программу, которая решает эту задачу за время O(N log N).
Входные данные:
Первый список для времени прибытия бронирования.
Второй список для времени отправления бронирования.
Третий - это K, который обозначает количество комнат.
Возвращает:
true, если есть достаточно номеров для N бронирования
false, если недостаточно номеров для N бронирования
Мой подход:
Heapsort список прибытий, применяя те же изменения к отбытиям, чтобы сохранить отношения индекса. TreeSet используется для отслеживания следующего времени оформления заказа. Для каждой итерации: гость регистрируется, а время выезда добавляется в TreeSet. Если произошла проверка, гость удаляется, а следующая проверка опрашивается из TreeSet. Если когда-либо происходит избыточное бронирование, возвращается false.
Мое решение работает в NetBeans, но дает сбой, когда я запускаю его через веб-сайт. Будем очень признательны за любую помощь.
Исходный вопрос: 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