Algorithm interview from Google

Question

I am a long time lurker, and just had an interview with Google where they asked me this question:

Various artists want to perform at the Royal Albert Hall and you are responsible for scheduling their concerts. Requests for performing at the Hall are accommodated on a first come first served policy. Only one performance is possible per day and, moreover, there cannot be any concerts taking place within 5 days of each other

Given a requested time d which is impossible (i.e. within 5 days of an already sched- uled performance), give an O(log n)-time algorithm to find the next available day d2 (d2 > d).

I had no clue how to solve it, and now that the interview is over, I am dying to figure out how to solve it. Knowing how smart most of you folks are, I was wondering if you can give me a hand here. This is NOT for homework, or anything of that sort. I just want to learn how to solve it for future interviews. I tried asking follow up questions but he said that is all I can tell you.

Answer 1

You need a normal binary search tree of intervals of available dates. Just search for the interval containing d. If it does not exist, take the interval next (in-order) to the point where the search stopped.

Note: contiguous intervals must be fused together in a single node. For example: the available-dates intervals {2 - 15} and {16 - 23} should become {2 - 23}. This might happen if a concert reservation was cancelled.

Alternatively, a tree of non-available dates can be used instead, provided that contiguous non-available intervals are fused together.