• I saw many posts using O(maxNumbers) space. Here I offer a link list approach that consumes less space. The idea is simple: maintaining a link list of available chunks, e.g., [0,9]->[15,19]->[21,100]...

class Record {
public:
Record(int b, int e) { beg = b; end = e; next = NULL; }
int beg, end;   // available numbers [beg, end]
Record *next;
};

class PhoneDirectory {
public:
/** Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
PhoneDirectory(int maxNumbers) {
if (maxNumbers < 1) head = NULL;
else head = new Record(0, maxNumbers - 1);
}

/** Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available. */
int get() {
}
return res;
}

/** Check if a number is available or not. */
bool check(int number) {
while (p) {
if (number >= p->beg && number <= p->end) return true;
else if (number < p->beg) break;
p = p->next;
}
return false;
}

/** Recycle or release a number. */
void release(int number) {
Record *p = head, *pre = NULL, *next;
while (p) {
next = p->next;

if (number < p->beg - 1) {
break;
}
else if (number == p->beg - 1) {
p->beg--;
return;
}
else if (number >= p->beg && number <= p->end) {
return;  // this number has not been assigned yet
}
else if (number == p->end + 1) {
p->end++;
if (next && p->end == next->beg) {
p->end = next->end;
p->next = next->next;
delete next;
}
return;
}
else {
pre = p;
p = next;
}
}

Record *node = new Record(number, number);  // need a new node
node->next = p;