"Nearest gap" doesn't sounds like a range query to me. It sounds more like a nearest neighbor query. It sounds like you have (start time, duration) tuples and want to search for nearest neighbor on start time with an at-least-X constraint on duration. (start time, duration) is more point-like than interval-like (as far as data structures go), so anything that can handle nearest neighbor on point-like data would be a candidate. If this is an accurate mapping for your problem, you might check out KD trees. You'd probably have to write a custom tree traversal algorithm to query NN on one dimension and >X on the other, but I think it could be done. Sounds kinda fun.

There are so many nuances here, but perhaps you could maintain two coalescing structures: what's free and what's used, complements one one another. Adding to one means removing from the other. One might give you a more constrained search space than the other.

An ordered structure feels like the way to go, here, since you said "nearest gaps". Once you know the time you'll get locality in your search. You could also run the search in both directions on two threads.