Dato un intervallo numerico e un elenco di numeri usati che rientrano in tale intervallo, ho bisogno di comprimere l'intervallo in blocchi di numeri usati e non utilizzati.
Ad esempio:
range: 0 to 10
used: 3,4,5,9
Ho bisogno di un output come
0-2: free
3-5: used
6-8: free
9: used
10: free
Non sai da dove cominciare, quindi ogni consiglio è apprezzato.
Come ho commentato, questo è molto simile alla codifica della lunghezza di esecuzione , infatti se used è ordinata è discutibilmente un po 'più facile!
Con la codifica della lunghezza di esecuzione si inizia con il primo numero in una matrice e si esegue la scansione in avanti contando il numero tra ciascuna transizione tra usato / non utilizzato (o nel caso si registra l'indice iniziale e finale che è essenzialmente equivalente).
Tuttavia, se usato è ordinato, sai già dove la prima transizione da inutilizzato- > usato è così puoi iniziare lì e scansionare used per la prossima transizione da used- > inutilizzato, quindi conosci anche il prossimo non usato - > utilizzato transizione come il prossimo used numero.
se used non è ordinato puoi ordinarlo prima (probabilmente una buona idea se usato è piccolo rispetto a range ) oppure potresti usare range e used per costruire prima un array completo di numeri usati e non usati es 00011100010 e lunghezza di esecuzione codifica questo.
Leggi altre domande sui tag algorithms