compress range of numbers into blocks of used or unused

Question

given a numerical range and a list of used numbers that fall within that range I need to compress the range into blocks of used and unused numbers. for example

range: 0 to 10
used:  3,4,5,9

i need an output like

0-2: free
3-5: used
6-8: free
9:   used
10:  free

Not sure where to start with this, so any guidance appreciated.

Answer 1

As I commented, this is very similar to run length encoding, in fact if used is sorted it is arguably a bit easier!

With run length encoding you would start with the first number in an array and scan forward counting the number between each transition between used/unused (or in your case recording the start and end index which is essentially equivalent).

However if used is sorted you already know where the first transition from unused->used is so you can start there and scan used for the next transition from used->unused, you then also know the next unused->used transition as its the next used number.

if used isn't sorted you could either sort it first (likely a good idea if used is small compared to range) or you could use range and used to first construct a full array of used and unused numbers e.g. 00011100010 and run length encode this.