Published on

The Algorithm Design Manual (3rd) Exercise Solution 'E3-30'

Table of Contents

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 3-30

Question

You are consulting for a hotel that has n one-bed rooms. When a guest checks in, they ask for a room whose number is in the range [l, h]. Propose a data structure that supports the following data operations in the allotted time:

(a) Initialize(n)Initialize(n): Initialize the data structure for empty rooms numbered
1, 2,...,n, in polynomial time.
(b) Count(l,h)Count(l, h): Return the number of available rooms in [l, h], in O(logn)O(log n) time.
(c) Checkin(l,h)Checkin(l, h): In O(logn)O(log n) time, return the first empty room in [l, h] and mark it occupied, or return NIL if all the rooms in [l, h] are occupied.
(d) Checkout(x)Checkout(x): Mark room x as unoccupied, in O(logn)O(log n) time.

Solution

Solution1

We can use Segment tree for this kind of problems where our concern is information that spans the range of the array.
Each leaf has room occupation flag and we use normal Segment tree searching and modifying operations, which are guaranteed to be run in O(logn)O(logn) time.

Solution2

Since we need cumulative information of range, we can use ordinal binary search tree with each node having additional information of sum of numbers of available rooms in its left subtree.

Here we use partial sum S(n), where S(n) denotes the sum of available rooms in a range of [0, n].

For example, if we want to count the number of available rooms in [l, h], we calculate two partial sums and subtract one from the other, say, count(l,h)=S(h)−S(l−1)count(l,h) = S(h) - S(l-1).

Comparison of solutions

Solution1 is easy for people who already know how Segment tree works, but use extra memory for not-leaf nodes.

Solution2 use exactly the same numbers of node as the number of elements in the original array. But its nodes have to have extra information about the sum of available rooms in the left subtree, and each operation is slightly more complicated than them of Solution1.

Code

Solution1
// Segment-tree strategy

#include <cassert>
#include <vector>
class Hotel_room_allotter {
   private:
    std::vector<int> availables;
    int n;
    constexpr static int get_i_l_chld(int i) { return 2 * i + 1; }
    constexpr static int get_i_r_chld(int i) { return 2 * i + 2; }

    void build(int i, int tl, int tr) {
        if (tl == tr) {
            availables[i] = 1;
            return;
        }
        auto tm{(tl + tr) / 2};
        auto i_l_chld{get_i_l_chld(i)};
        auto i_r_chld{get_i_r_chld(i)};
        build(i_l_chld, tl, tm);
        build(i_r_chld, tm + 1, tr);
        availables[i] = availables[i_l_chld] + availables[i_r_chld];
    }

   public:
    Hotel_room_allotter(int _n) : n{_n} {
        availables.resize(n * 3);
        build(0, 0, n - 1);
    }
    int count_helper(int i, int tl, int tr, int l, int h) const {
        if (h < l) return 0;
        if (tl == l && tr == h) return availables[i];
        auto tm{(tl + tr) / 2};
        auto i_l_chld{get_i_l_chld(i)};
        auto i_r_chld{get_i_r_chld(i)};
        return count_helper(i_l_chld, tl, tm, l, std::min(tm, h)) +
               count_helper(i_r_chld, tm + 1, tr, std::max(tm + 1, l), h);
    }
    int count(int l, int h) const { return count_helper(0, 0, n - 1, l, h); }
    int checkin(int l, int h) {
        int i{0};
        int tl{0};
        int tr{n - 1};
        std::vector<int *> nodes_in_the_way;
        while (tl != tr) {
            auto tm{(tl + tr) / 2};
            auto i_l_chld{get_i_l_chld(i)};
            auto i_r_chld{get_i_r_chld(i)};
            nodes_in_the_way.push_back(&availables[i]);
            if (l <= tm && availables[i_l_chld]) {
                i = i_l_chld;
                tr = tm;
                h = std::min(tm, h);
            } else if (tm < h && availables[i_r_chld]) {
                i = i_r_chld;
                tl = tm + 1;
                l = std::max(tm + 1, l);
            } else
                return -1;
        }
        if (availables[i]) {
            --availables[i];
            for (auto nd : nodes_in_the_way) --*nd;
            return tl;
        }
        return -1;
    }

    bool checkout(int x) {
        int i{0};
        int tl{0};
        int tr{n - 1};
        std::vector<int *> nodes_in_the_way;
        while (tl != tr) {
            auto tm{(tl + tr) / 2};
            auto i_l_chld{get_i_l_chld(i)};
            auto i_r_chld{get_i_r_chld(i)};
            nodes_in_the_way.push_back(&availables[i]);
            if (x <= tm) {
                i = i_l_chld;
                tr = tm;
            } else {
                i = i_r_chld;
                tl = tm + 1;
            }
        }
        if (availables[i])
            return false;
        else {
            availables[i] = 1;
            for (auto nd : nodes_in_the_way) ++*nd;
        }
        return true;
    }
};

int main(int argc, char const *argv[]) {
    Hotel_room_allotter ha{1};
    assert(ha.count(0, 0) == 1);
    assert(ha.checkin(0, 0) == 0);
    assert(ha.checkin(0, 0) == -1);
    assert(ha.count(0, 0) == 0);
    assert(ha.checkout(0));
    assert(ha.count(0, 0) == 1);
    assert(!ha.checkout(0));
    assert(ha.count(0, 0) == 1);

    ha = (2);
    assert(ha.count(0, 0) == 1);
    assert(ha.count(1, 1) == 1);
    assert(ha.count(0, 1) == 2);
    assert(ha.checkin(0, 0) == 0);
    assert(ha.count(0, 0) == 0);
    assert(ha.count(0, 1) == 1);
    assert(ha.checkout(0));
    assert(ha.count(0, 0) == 1);
    assert(ha.count(0, 1) == 2);
    assert(ha.checkin(1, 1) == 1);
    assert(ha.count(0, 1) == 1);
    assert(ha.count(1, 1) == 0);
    assert(ha.checkout(1));
    assert(ha.count(0, 1) == 2);
    assert(ha.count(1, 1) == 1);
    assert(ha.checkin(0, 1) == 0);
    assert(ha.count(0, 1) == 1);
    assert(ha.checkin(0, 1) == 1);
    assert(ha.count(0, 1) == 0);
    assert(ha.checkout(0));
    assert(ha.checkin(1, 1) == -1);
    assert(ha.count(0, 1) == 1);

    ha = (5);
    assert(ha.checkin(0, 2) == 0);
    assert(ha.count(0, 4) == 4);
    assert(ha.checkin(0, 2) == 1);
    assert(ha.count(0, 4) == 3);
    assert(ha.checkin(0, 2) == 2);
    assert(ha.count(0, 4) == 2);

    assert(ha.checkin(0, 2) == -1);
    assert(ha.count(0, 4) == 2);

    assert(ha.checkin(0, 4) == 3);
    assert(ha.count(0, 4) == 1);
    assert(ha.checkin(0, 4) == 4);
    assert(ha.count(0, 4) == 0);

    assert(ha.checkout(0));
    assert(ha.count(0, 4) == 1);
    assert(!ha.checkout(0));
    assert(ha.count(0, 4) == 1);
    assert(ha.checkout(1));
    assert(ha.count(0, 4) == 2);
    assert(ha.checkout(2));
    assert(ha.count(0, 4) == 3);
    assert(ha.checkout(3));
    assert(ha.count(0, 4) == 4);
    assert(ha.checkout(4));
    assert(ha.count(0, 4) == 5);

    ha = (8);
    assert(ha.count(0, 7) == 8);
    assert(ha.count(1, 5) == 5);
    assert(ha.count(2, 6) == 5);

    assert(ha.checkin(1, 3) == 1);
    assert(ha.count(1, 5) == 4);
    assert(ha.checkin(2, 4) == 2);
    assert(ha.count(1, 5) == 3);

    assert(ha.checkout(1));
    assert(ha.count(1, 5) == 4);
    assert(ha.checkout(2));
    assert(ha.count(1, 5) == 5);
    assert(ha.checkin(7, 7) == 7);
    assert(ha.count(0, 7) == 7);
    assert(ha.checkin(7, 7) == -1);
    assert(ha.count(0, 7) == 7);

    ha = (13);
    assert(ha.count(11, 11) == 1);
    assert(ha.count(12, 12) == 1);

    ha = (264);
    assert(ha.count(0, 63) == 64);
    assert(ha.count(55, 222) == 168);
    assert(ha.count(128, 263) == 136);

    return 0;
}
Solution2
// Storing sum-of-left-room tree strategy

#include <cassert>
#include <vector>
struct roomnode {
    bool availability{true};
    int sum_of_left_room{0};
};

class Hotel_room_allotter {
   private:
    std::vector<roomnode> availables;
    constexpr static int i_root(const int l, const int r) {
        return (l + r) / 2;
    }
    constexpr static int av2num(bool av) { return static_cast<int>(av); }

    int build(int l, int r) {
        if (r < l) return 0;
        if (l == r) return 1;
        auto pos{i_root(l, r)};
        availables[pos].sum_of_left_room = build(l, pos - 1);
        return availables[pos].sum_of_left_room + 1 + build(pos + 1, r);
    }

   public:
    Hotel_room_allotter(int _n) : availables(_n) { build(0, _n - 1); }
    int partial_sum(int i) const {
        if (i < 0) return 0;

        int total_cnt{0};
        int l{0};
        int r{static_cast<int>(availables.size()) - 1};
        while (l <= r) {
            auto pos{i_root(l, r)};
            if (i < pos)
                r = pos - 1;
            else if (i == pos) {
                total_cnt += availables[pos].sum_of_left_room +
                             av2num(availables[pos].availability);
                break;
            } else {
                total_cnt += availables[pos].sum_of_left_room +
                             av2num(availables[pos].availability);
                l = pos + 1;
            }
        }
        return total_cnt;
    }
    int count(int l, int h) const {
        return partial_sum(h) - partial_sum(l - 1);
    }
    int checkin(int l, int h) {
        int tl{0};
        int tr{static_cast<int>(availables.size()) - 1};
        std::vector<roomnode *> nodes_in_the_way;
        while (true) {
            auto tm{i_root(tl, tr)};
            if (l < tm && availables[tm].sum_of_left_room) {
                nodes_in_the_way.push_back(&availables[tm]);
                tr = tm - 1;
            } else if (l <= tm && tm <= h && availables[tm].availability) {
                tl = tm;
                break;
            } else if (tm < h) {
                tl = tm + 1;
            } else
                return -1;
        }
        availables[tl].availability = !availables[tl].availability;
        for (auto nd : nodes_in_the_way) --nd->sum_of_left_room;
        return tl;
    }

    bool checkout(int x) {
        int tl{0};
        int tr{static_cast<int>(availables.size()) - 1};
        std::vector<roomnode *> nodes_in_the_way;
        int tm;
        while ((tm = i_root(tl, tr)) != x) {
            if (x < tm) {
                nodes_in_the_way.push_back(&availables[tm]);
                tr = tm - 1;
            } else {
                tl = tm + 1;
            }
        }
        if (availables[x].availability)
            return false;
        else {
            availables[x].availability = !availables[x].availability;
            for (auto nd : nodes_in_the_way) ++nd->sum_of_left_room;
        }
        return true;
    }
};

int main(int argc, char const *argv[]) {
    Hotel_room_allotter ha{1};
    assert(ha.count(0, 0) == 1);
    assert(ha.checkin(0, 0) == 0);
    assert(ha.checkin(0, 0) == -1);
    assert(ha.count(0, 0) == 0);
    assert(ha.checkout(0));
    assert(ha.count(0, 0) == 1);
    assert(!ha.checkout(0));
    assert(ha.count(0, 0) == 1);

    ha = (2);
    assert(ha.count(0, 0) == 1);
    assert(ha.count(1, 1) == 1);
    assert(ha.count(0, 1) == 2);
    assert(ha.checkin(0, 0) == 0);
    assert(ha.count(0, 0) == 0);
    assert(ha.count(0, 1) == 1);
    assert(ha.checkout(0));
    assert(ha.count(0, 0) == 1);
    assert(ha.count(0, 1) == 2);
    assert(ha.checkin(1, 1) == 1);
    assert(ha.count(0, 1) == 1);
    assert(ha.count(1, 1) == 0);
    assert(ha.checkout(1));
    assert(ha.count(0, 1) == 2);
    assert(ha.count(1, 1) == 1);
    assert(ha.checkin(0, 1) == 0);
    assert(ha.count(0, 1) == 1);
    assert(ha.checkin(0, 1) == 1);
    assert(ha.count(0, 1) == 0);
    assert(ha.checkout(0));
    assert(ha.checkin(1, 1) == -1);
    assert(ha.count(0, 1) == 1);

    ha = (5);
    assert(ha.checkin(0, 2) == 0);
    assert(ha.count(0, 4) == 4);
    assert(ha.checkin(0, 2) == 1);
    assert(ha.count(0, 4) == 3);
    assert(ha.checkin(0, 2) == 2);
    assert(ha.count(0, 4) == 2);

    assert(ha.checkin(0, 2) == -1);
    assert(ha.count(0, 4) == 2);

    assert(ha.checkin(0, 4) == 3);
    assert(ha.count(0, 4) == 1);
    assert(ha.checkin(0, 4) == 4);
    assert(ha.count(0, 4) == 0);

    assert(ha.checkout(0));
    assert(ha.count(0, 4) == 1);
    assert(!ha.checkout(0));
    assert(ha.count(0, 4) == 1);
    assert(ha.checkout(1));
    assert(ha.count(0, 4) == 2);
    assert(ha.checkout(2));
    assert(ha.count(0, 4) == 3);
    assert(ha.checkout(3));
    assert(ha.count(0, 4) == 4);
    assert(ha.checkout(4));
    assert(ha.count(0, 4) == 5);

    ha = (8);
    assert(ha.count(0, 7) == 8);
    assert(ha.count(1, 5) == 5);
    assert(ha.count(2, 6) == 5);

    assert(ha.checkin(1, 3) == 1);
    assert(ha.count(1, 5) == 4);
    assert(ha.checkin(2, 4) == 2);
    assert(ha.count(1, 5) == 3);

    assert(ha.checkout(1));
    assert(ha.count(1, 5) == 4);
    assert(ha.checkout(2));
    assert(ha.count(1, 5) == 5);
    assert(ha.checkin(7, 7) == 7);
    assert(ha.count(0, 7) == 7);
    assert(ha.checkin(7, 7) == -1);
    assert(ha.count(0, 7) == 7);

    ha = (13);
    assert(ha.count(11, 11) == 1);
    assert(ha.count(12, 12) == 1);

    ha = (264);
    assert(ha.count(0, 63) == 64);
    assert(ha.count(55, 222) == 168);
    assert(ha.count(128, 263) == 136);

    return 0;
}