来自谷歌的算法面试

Question

我潜伏了很长时间，刚刚接受了 Google 的采访，他们问了我这个问题:

各种艺术家想在皇家阿尔伯特音乐厅演出，您负责安排他们的音乐会。在大厅表演的请求以先到先得的方式安排政策。每天只能进行一场表演，而且不能举行任何音乐会相隔 5 天

给定一个不可能的请求时间 d(即在已经安排的 5 天内-uled performance), 给出一个 O(log n)-time 算法来找到下一个可用的日期 d2(d2 > d).

我不知道如何解决它，现在面试结束了，我很想知道如何解决它。知道你们中的大多数人有多聪明，我想知道你是否可以在这里帮我一把。这不是家庭作业，或任何类似的东西。我只是想学习如何解决它以备将来面试。我试着问后续问题，但他说我只能告诉你这些。

Answer 1

您需要可用日期间隔的普通二叉搜索树。只需搜索包含 d 的区间。如果不存在，则取下一个(按顺序)到搜索停止点的区间。

注意:连续的间隔必须在单个节点中融合在一起。例如:可用日期间隔 {2 - 15} 和 {16 - 23} 应变为 {2 - 23}。如果音乐会预订被取消，可能会发生这种情况。

或者，可以使用非可用日期树来代替，前提是将连续的非可用时间间隔融合在一起。