Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
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? –  Baqueta Jan 9 '13 at 17:27
1  
this is very similar to run length encoding ... –  jk. Jan 9 '13 at 17:28
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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