Integer assignment in range

Question

I'm looking for an algorithm that assigns and releases integers from some interval [a,b].

Every time we request an assignment, the algorithm produces an integer in the [a,b] range that has not been assigned before. We may free integers that had previously been assigned by asking the algorithm to release them. Doing so makes them available for assignment again.

To summarise:

• After an integer is assigned, it cannot be assigned again until it is released
• If one or more integers are not assigned, the algorithm must assign one of them
• If and only if all integers in the range are assigned, the algorithm assigns none

It is desired that both the time and space complexity of the algorithm be sub-linear (for n = b - a).

As a bonus requirement, assume that some specific integers in [a,b] are required to be initially assigned.

Answer 1

The first thing that comes to mind is start with a single "available" range. When the user assigns an integer, simply remove it from the range:

        [a,b]
a <---  [a+1,b]

This is an O(1) operation in all cases. Due to the way the return step works, this means that the maximum number is only assigned when no other number is available, and low numbers are reused as often as possible.

When the user returns an integer, do a binary search to figure out which range it either goes before, or merges into:

[28][30-50]     <---- user is going to release 29
[28-50]
-or-
[26][30-50]     <----- user is going to release 28
[26][28][30-50]

This is an O(log m) operation where m is the number of ranges, which is usually very small. It starts at 1, but can be at most n/2 depending on which numbers the user releases.

If you want to get really tricky, you can add an second ordering on the ranges, that moves smaller ranges closer toward the "front", and larger ranges closer to the "end", and when the user makes a number "available", you give them the first value in the "smallest" range, which would heuristically lead to smaller sets being "consumed", leaving fewer sets total, thus saving space on average. However, this adds a lot of complexity, and a small amount of space and time, so the worst cases get slightly worse. Measure first before trying this.

It's worth mentioning that this does use linear space, though I'm pretty sure the constant is <=1, so the memory overhead would be less than that of storing all of the numbers. It's hard to calculate an average without making wild assumptions about how the user assigns and releases integers, but I'm pretty sure the average memory usage is actually closer to logarithmic than linear. Hard to tell though, that might be optimism.

Some dynamic memory dispatches work on similar concepts to this, often storing the "unused" parts as a linked list inside the unused memory. This way, there's no additional overhead space required. Since you're dealing with integer ranges rather than heap memory, this optimization probably doesn't help you.