来自Google的算法访谈
我是一个很长时间的潜伏者，刚刚接受了Google的采访，他们问我这个问题：
各种艺术家都希望在皇家阿尔伯特音乐厅演出，并负责安排他们的音乐会。 在大会堂演出的要求以先到先得的方式提供。 每天只有一次表演，而且，在5天之内不可能举行任何音乐会
给定要求的时间d，这是不可能的（即在已经调度的性能的5天内），给出O（log n）时间算法以找到下一个可用天d2（d2> d）。
我不知道如何解决，现在面试结束了，我很想知道如何解决这个问题。 知道你们大多数人都很聪明，我想知道你能否在这里帮我一把。 这不适用于家庭作业或任何此类事情。 我只是想学习如何解决它为未来的采访。 我试着询问后续问题，但他说这就是我所能告诉你的。
您需要一个可用日期间隔的普通二分查找树。 只需搜索包含d的区间。 如果它不存在，则将下一个（按顺序）的间隔设置为搜索停止点。
注意：连续间隔必须在单个节点中融合在一起。 例如：可用日期间隔{2 - 15}和{16 - 23}应该变为{2 - 23}。 如果音乐会预订被取消，可能会发生这种情况
或者，可以使用不可用日期的树来代替，只要将连续的不可用间隔融合在一起即可。
将预定的音乐会存储在二叉搜索树中，并通过二分搜索找到可行的解决方案。
像这样的东西：
FindDateAfter(tree, x):
n = tree.root
if n.date < x
n = FindDateAfter(n.right, x)
else if n.date > x and n.left.date < x
return n
return FindDateAfter(n.left, x)
FindGoodDay(tree, x):
n = FindDateAfter(tree, x)
while (n.date + 10 < n.right.date)
n = FindDateAfter(n, n.date + 5)
return n.date + 5
我已经使用了一个二叉搜索树（BST），它保存可以安排表演的有效免费日的范围。 其中一个范围必须以int.MaxValue结尾，因为我们有无限的天数，所以它不能被绑定。
以下代码会搜索距离所需日期最近的一天，然后将其返回。
当H是树高时（通常H = log（N），但在某些情况下可以变为H = N），时间复杂度为O（H ）。 空间复杂度与时间复杂度相同。
public static int FindConcertTime(TreeNode<Tuple<int, int>> node, int reqDay)
{
// Not found!
if (node == null)
{
return -1;
}
Tuple<int, int> currRange = node.Value;
// Found range.
if (currRange.Item1 <= reqDay &&
currRange.Item2 >= reqDay)
{
// Return requested day.
return reqDay;
}
// Go left.
else if (currRange.Item1 > reqDay)
{
int suggestedDay = FindConcertTime(node.Left, reqDay);
// Didn't find appropriate range in left nodes, or found day
// is further than current option.
if (suggestedDay == -1 || suggestedDay > currRange.Item1)
{
// Return current option.
return currRange.Item1;
}
else
{
// Return suggested day.
return suggestedDay;
}
}
// Go right.
// Will always find because the right-most node has "int.MaxValue" as Item2.
else //if (currRange.Item2 < reqDay)
{
return FindConcertTime(node.Right, reqDay);
}
}