来自谷歌的算法面试
我是一个潜伏了很长时间的人，刚刚接受了谷歌的采访，他们问了我这个问题：
许多艺术家都想在皇家阿尔伯特音乐厅演出，你负责安排他们的演唱会。在音乐厅演出的要求将以先到先得的方式提供服务。每天只能有一场演出，而且不能在5天内举行任何音乐会。
给定一个不可能的请求时间d(即，在已经调度的性能的5天内)，给出一个O(log )-time算法来找到下一个可用天d2 (d2 > d)。
我不知道如何解决它，现在面试结束了，我渴望知道如何解决它。我知道你们大多数人都很聪明，我想知道你们能不能帮我个忙。这不是用来做家庭作业的，或者类似的东西。我只想学习如何在将来的面试中解决这个问题。我试着问一些后续问题，但他说我只能告诉你这些。
回答 8
Stack Overflow用户
发布于 2013-02-28 12:55:16
您需要一个包含可用日期间隔的普通二进制搜索树。只搜索包含d的间隔。如果不存在，则将该间隔(按顺序)取到搜索停止的点。
注意:连续的间隔必须在单个节点中融合在一起。例如:可用日期间隔{2 - 15}和{16 - 23}应变为{2 - 23}。如果取消了演唱会预订，可能会发生这种情况。
或者，如果连续的不可用间隔被融合在一起，则可以使用不可用日期树来代替。
Stack Overflow用户
发布于 2013-02-28 10:27:36
将预定的演唱会存储在binary search tree中，并通过二进制搜索找到可行的解决方案。
如下所示：
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 + 5Stack Overflow用户
发布于 2017-02-12 23:25:33
我使用了一个二进制搜索树(BST)，它保存了可以安排演出的有效空闲天数的范围。其中一个范围必须以int.MaxValue结束，因为我们有无限的天数，所以它不能被绑定。
下面的代码搜索最接近请求日期的日期，然后返回该日期。
当H为树高时，时间复杂度为O(H) (通常为H=log(N)，但在某些情况下可以变为H=N )。空间复杂度与时间复杂度相同。
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);
}
}https://stackoverflow.com/questions/15126325
复制相似问题
腾讯云开发者
