Re: Encoding/decoding ranges of unsigned integers...

John Reiser wrote: 
Assume you have n integer ranges: [i, j], [k, l], [m, n]...

There is no particular order on the sequence of ranges.
There is no gap in any of the ranges.



If "no gap" implies that the given intervals are a partition
(disjoint cover) of the interval [min(i,k,m,...), max(j,l,n,...)]:
Sort the intervals, then encode one of the endpoints of
the large interval, and the ordered sequence of lengths
of the sorted subintervals.


Hi John,

Thanks for offering your thoughts.

1)

"no gap" does not mean this in this case.
I guess I have used this expression too casually.

There are 2 sample ranges:

[2-5] = [2,3,4,5]

[7-7] = [7]

"no gap" in any single range is what I meant. So, this is not a valid range:

[2,4,5] (3 is missing)

2)

No, it's not a disjoint cover.

If you were to sort a sample set of ranges, you could have something like this:

[2-3], [5-12], [14-17], [20-45], [46-112], [114-456], etc...

Hence, it's not a cover and the density of ranges is higher at the beginning of the sorted sequence.
.

Relevant Pages