来自Google的算法访谈

Question

我是一个很长时间的潜伏者,只是接受了谷歌的采访,他们问我这个问题:

各种艺术家都想在皇家阿尔伯特音乐厅演出,你负责安排他们的音乐会.在大厅表演的要求按照先到先得的政策进行.每天只能进行一次演出,此外,不能在5天内举行任何音乐会

给定一个不可能的请求时间d(即在已经计划的性能的5天内),给出O(log n)时间算法以找到下一个可用日d2(d2> d).

我不知道如何解决它,现在面试已经结束,我很想知道如何解决它.知道你们大多数人的聪明才智,我想知道你能否在这里帮助我.这不是作业,或任何类似的东西.我只是想学习如何解决它以便将来的采访.我试着提出跟进问题,但他说这就是我可以告诉你的全部内容.

Answer 1

您需要一个可用日期间隔的普通二进制搜索树.只需搜索包含d的区间.如果它不存在,请将下一个间隔(按顺序)移至搜索停止的位置.

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

或者,如果连续的不可用间隔融合在一起,则可以使用不可用日期的树.

Answer 2

将预定的音乐会存储在二叉搜索树中，并通过二分搜索找到可行的解决方案。

像这样的东西：

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