Since you are already maintaining an external map of category=lower-upper, I'd try to avoid frequent cluster changes. The easiest way is to add another field in your map for last used, or next free.
Another option is to generate next ID on the fly. Here is an example of shell way, you can, of...