- I'd like to acquire <resource> at time T for N units of time.
- I'd like to acquire <resource> for N units of time, give me possible T's.
First, it's was a great benefit to identify what "unit of time" was. For my case it was 30 minutes; this helped tremendously as you'll see.
Next, for the first question (I want <resource> at time T), once I had enough data that actually searching became slow enough such that a return of "resource not available" became problematic, I found a bloom filter seriously improved things. It allowed for not only the common case fails to fail really fast, but bit-shifting the filter also allowed for some very fast parallel queries of "nearby" time slots. I was able to rapidly return things like "2pm isn't available, but 1:30pm is".
Last, for the second question (I'd like <resource> for N units of time), this is _very_ similar to a heap memory allocator. At its simplest it's just a b-tree of slots, etc. Grabbing a big slot, splitting it up, etc. This gets even easier if there are time boundaries that cannot be crossed (eg, a day).
To be clear, the allocator approach isn't about you managing a BTree like you have been. It's about a tree of _available_ time slots that are _free_. Initially it begins as a tree with a single node for all time. Make a request, scan the tree for a time slot large enough to meet the length needed, subdivide it, etc. If a time slot is not longer needed, you put it back into the tree by scanning for the node it belongs to (or fits between), coalescing, etc.
Hope this helps!