[hyperpape]

What if you structure the "lists" so that each "freelist" contains all slots >= 2^n units of time? Then you only ever need to search the list that's the next size down from your target slot?

This will be bad for write performance, but solves the problem of needing to do multiple searches to find the next available slot, and you mentioned that you might not mind sacrificing write performance.

[grovesNL]

That's definitely possible and could be a reasonable tradeoff. I'd be slightly worried about the extent that it sacrifices write performance, but it might not be too bad if if the number of levels are kept small.