379. Design Phone Directory (Medium)

Design a Phone Directory which supports the following operations:

1. get: Provide a number which is not assigned to anyone.
2. check: Check if a number is available or not.
3. release: Recycle or release a number.

Example:

// Init a phone directory containing a total of 3 numbers: 0, 1, and 2.
PhoneDirectory directory = new PhoneDirectory(3);

// It can return any available phone number. Here we assume it returns 0.
directory.get();

// Assume it returns 1.
directory.get();

// The number 2 is available, so return true.
directory.check(2);

// It returns 2, the only number that is left.
directory.get();

// The number 2 is no longer available, so return false.
directory.check(2);

// Release number 2 back to the pool.
directory.release(2);

// Number 2 is available again, return true.
directory.check(2);

Solution:

version 1: 1665ms the trick of freeList[--index] = number;

class PhoneDirectory {
public:
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    PhoneDirectory(int maxNumbers): count(maxNumbers), idx(0), freeFlag(maxNumbers, true), freeList(maxNumbers) {
        for (int i = 0; i < maxNumbers; ++i) {
            freeList[i] = i;
        }
    }

    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    int get() {
        if (idx < count) {
            int n = freeList[idx++];
            freeFlag[n] = false;
            return n;
        } else return -1;
    }

    /** Check if a number is available or not. */
    bool check(int number) {
        if (number < 0 || number >= count) return false;
        return freeFlag[number];
    }

    /** Recycle or release a number. */
    void release(int number) {
        if (number < 0 || number >= count || freeFlag[number]) return;
        freeFlag[number] = true;
        freeList[--idx] = number;
    }
private:
    int count, idx;
    vector<bool> freeFlag;
    vector<int> freeList;
};

/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj.get();
 * bool param_2 = obj.check(number);
 * obj.release(number);
 */

version 2: TLE

class PhoneDirectory {
public:
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    PhoneDirectory(int maxNumbers): idx(0), count(maxNumbers) {

    }

    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    int get() {
        if (recycle.empty() && idx >= count) return -1;
        if (recycle.empty() || *recycle.begin() > idx) return idx++;
        int num = *recycle.begin();
        if (num == idx) ++idx;
        recycle.erase(recycle.begin());
        return num;
    }

    /** Check if a number is available or not. */
    bool check(int number) {
        if ((number < count && number >= idx) || recycle.count(number)) return true;
        return false;
    }

    /** Recycle or release a number. */
    void release(int number) {
        if (number < 0 || number >= count || recycle.count(number)) return;
        recycle.insert(number);
    }
private: 
    int idx, count;
    set<int> recycle;
};