It sounds like you should precompute the duration available at offsets, and let yourself, not simply: search for the first good enough slot; but: retrieve the smallest satisfying interval from a list, precomputed to some acceptable count.

If it's not worth doing that pre-computation, as your trials have shown and others say, ordered maps might be the best available.