InterviewBit: возможно бронирование отелей. Решение работает в IDE, но не на сайте

Менеджер отеля должен обработать 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

person Duy Đặng    schedule 12.04.2017    source источник
comment
но не работает, когда я запускаю его через веб-сайт - определить   -  person Scary Wombat    schedule 12.04.2017
comment
Тестовый сценарий в конце моего алгоритма — это когда мой код дал сбой на веб-сайте. Он печатает ожидаемое значение, когда я запускаю его в NetBeans.   -  person Duy Đặng    schedule 12.04.2017


Ответы (2)


заменил TreeSet на TreeMap, так как повторяющиеся времена проверки были потеряны.

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;
}
person Duy Đặng    schedule 12.04.2017

Я бы предложил вместо использования древовидной карты и всех структур данных, использующих обычную логику в данном массиве, решить эту проблему.

public class Solution { public boolean hotel(ArrayList<Integer> arrive, ArrayList<Integer> depart, int K) { Collections.sort(arrive); Collections.sort(depart); int roomsRequired=0,i=0,j=0; while(i<arrive.size() && j<arrive.size() && roomsRequired<=K){ if(arrive.get(i)<depart.get(j) ){ i++; roomsRequired++; }else{ j++; roomsRequired--; } } if(roomsRequired<=K){ return true; }else{ return false; } } }

person Ark    schedule 18.10.2017