CSES - Hotel Queries

 Problem Link

Time Complexity: O(N log N + M log N)
Algorithm Used: Dynamic Range Maximum Queries, Segment Tree

In this problem, a list of hotels is given, each having Hᵢ rooms. Then a list of people are given, each wanting Pᵢ rooms. Then people must be processed in the order given and for each group, the first available hotel must be assigned. Then the number of rooms available in that hotel decreases by the number of rooms taken.

This problem uses Dynamic Range Maximum Queries. A segment tree can be used for this purpose. For each group of people, we walk down the segment tree, starting from the top node. Each node in the tree will have 2 children except for the leaves. We check both the children and choose the first of the two children (the first hotel) which has at least the number of rooms required by the group. This continues until a leaf is found.  If neither of the children have enough rooms for the group, then none of the hotels will have enough rooms, so the program prints 0 in this case. 

After finding the appropriate hotel, we need to update the segment tree with the new numbers. Decrement the number of rooms available in the chosen hotel by the number of rooms booked by the group and then recalculate the maximum range for the tree using a standard segment tree update function.

Code

#include <bits/stdc++.h>

using namespace std;

int seg_size;

vector<int> seg_tree;

void update_available_hotels(int x, int rooms) {

    seg_tree[x] -= rooms;

    for (x /= 2; x > 0; x /= 2)

        seg_tree[x] = max(seg_tree[x * 2], seg_tree[x * 2 + 1]);

}

int main()

{

    int n, m;

    cin >> n >> m;

    vector<int> hotels(n);

    for (int i = 0; i < n; i++)

        cin >> hotels[i];

   

    seg_size = pow(2, ceil(log2(n)));

    seg_tree.resize(2 * seg_size);

    for (int i = seg_size; i < seg_size + n; i++)

        seg_tree[i] = hotels[i - seg_size];

   

    for (int i = seg_size - 1; i > 0; i--) {

        seg_tree[i] = max(seg_tree[i*2], seg_tree[i*2 + 1]);

    }

    for (int i = 0; i < m; i++) {

        int rooms, j = 1;

        cin >> rooms;

        while (j < seg_size) {

            if (seg_tree[j * 2] >= rooms) {

                j = j * 2;

            } else if (seg_tree[j * 2 + 1] >= rooms) {

                j = j * 2 + 1;

            } else {

                break;

            }

        }

        if (seg_tree[j] < rooms) {

            cout << 0 << ' ';

            continue;

        } else {

            cout << j - seg_size + 1 << ' ';

            update_available_hotels(j, rooms);

        }

    }

    cout << '\n';

}