InterviewBit：酒店预订可能。解决方案适用于 IDE 但不适用于网站

Question

一位酒店经理必须处理 N 个下一季的房间预订。他的旅馆有K个房间。预订包含到达日期和离开日期。他想了解酒店是否有足够的房间来满足需求。写一个程序在时间 O(N log N) 内解决这个问题。

输入：
预定到达时间第一表。
预订出发时间的第二个列表。
第三个是 K，表示房间数。

Returns:
如果有足够的房间供 N 个预订，则为 true
如果没有足够的房间供 N 个预订，则为 false

我的做法：
堆排序到达列表，应用相同的更改离开以维护索引关系。 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

Answer 1

由于丢失了重复的结帐时间，因此用 TreeMap 替换了 TreeSet。

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

Answer 2

我建议不要使用树图，所有在给定数组列表上使用正常逻辑的数据结构都可以解决这个问题。

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