If time intervals are truly discrete and you don't need to union two different sets of time intervals, then you can keep track of free time intervals and schedu

If time intervals are truly discrete and you don't need to union two different sets of time intervals, then you can keep track of free time intervals and scheduled times separately. For a wide variety of time slots, keep separate start-time-ordered maps of free slots of size 2^n-1 to 2^(n+1) and search smallest possible first which should be O( log_2 (buckets)) for earliest-possible or O(log N) for arbitrary desired start time, assuming number of buckets isn't too huge. I'm curious if a heap would be faster than a btree; I think the speed tradeoff is how long it takes to re-add the portion of the free space back to the data structure. With luck, a btree should only need to move a free space entry within a single node which should be very fast. If appointments are cancelled, insert an appropriately-sized free space into the data structure. Coalesce adjacent free space (probably fastest in a btree) and move to a larger size bucket if necessary. For high concurrency also use a rotating series of buckets by time interval so that you can entirely drop structures once they have aged off (maximum time interval end is less than now() ), with your free space at the end of each bucket overlapping the next to at least the duration of the maximum appointment length with special case handling to allow an appointment to overlap two buckets (shrinking free space in both). This should allow full multithreaded processing unless every reservation is soonest-available-appointment. Appointments can live in a hash by their key or ID with their (start,end) interval as the value for O(1) lookups on appointment deletion. As others have pointed out it's a lot like malloc algorithms with the constraint that you care about address order (time). So linked lists of free buckets of size 2^k become time-ordered maps, and rotating ephemeral maps to account for unbounded time plus the analog of thread-local storage for concurrency.