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.

  • 2
    Have you written any code or pseudocode yet? Please post what you have tried. – default.kramer Jan 9 '13 at 17:27
  • 2
    Is the list of used numbers ordered? – vaughandroid Jan 9 '13 at 17:27
  • 1
    this is very similar to run length encoding ... – jk. Jan 9 '13 at 17:28

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.

  • I've sorted this in a simple way by just scanning the the whole range and checking if every number is in used. as the size of range and used is small this is inexpensive. Thanks – Chris Blackwell Jan 11 '13 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.