Totally agree with other comments that a sorted array will be hard to beat. I don't see how binary search could help with the "look for the next availability" query, but even a linear search could be fast on a strong CPU with cache prefetching, out-of-order execution, etc.

A few thousand elements is still small for a computer. I would be curious to see a benchmark comparing sorted arrays of intervals against the fancier structures.