15

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

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

给定一个不可能的请求时间 d（即在已经安排好的表演的 5 天内），给出一个 O(log n) 时间的算法来找到下一个可用的日期 d2 (d2 > d)。

我不知道如何解决它，现在面试结束了，我很想弄清楚如何解决它。知道你们大多数人有多聪明，我想知道您是否可以在这里帮帮我。这不适用于家庭作业或任何类似的东西。我只是想学习如何在以后的面试中解决它。我试着问后续问题，但他说这就是我能告诉你的全部。

4

8 回答 8

9

您需要一个正常的可用日期间隔的二叉搜索树。只需搜索包含 d 的区间。如果不存在，则将间隔 next（按顺序）到搜索停止的点。

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

或者，如果将连续的不可用间隔融合在一起，则可以使用不可用日期树来代替。

于 2013-02-28T04:55:16.070 回答
4

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

像这样的东西：

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
于 2013-02-28T02:27:35.743 回答
2

我使用了一个二叉搜索树 (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);
    }
}
于 2017-02-12T15:25:32.830 回答
0

上面已经提到过，但基本上用二叉树保持简单。您知道二叉树的复杂度为 log N。所以你已经知道你需要使用什么算法。您所要做的就是提出一个树节点结构并使用二叉​​树插入算法来查找下一个可用日期： 可能的一种：树节点有两个属性：d（音乐会日期）和 d+5（结束锁定期为 5 天的日期）。再次为简单起见，对两个日期属性使用时间戳。现在通过使用初始条件为 root = null 的二叉树中序插入算法找到下一个可用日期是微不足道的。

于 2015-03-16T06:51:36.490 回答
0

存储每年、每季度和每月的使用夜数。要查找免费住宿，请先查找未订满的第一年，然后查找该年内的季度，然后查找月份。然后检查那个月的每个晚上。

日历系统中的不规则性使这有点棘手，因此您可以将 4 晚作为“月”，将 16 晚作为“季度”，等等，而不是使用年和月。

于 2013-02-28T06:55:43.203 回答
0

Assume, at level 1 all schedule details are available. Group schedule of 16 days schedule at level 2. Group 16 level 2 status at level 3. Group 16 level 3 status at level 4. Depends on number of days that you want to expand, increase the level.

Now search from higher level and do binary search at the end.

于 2014-08-09T20:12:45.183 回答
0

渐近复杂度：- 这意味着运行时间随着输入的增长而变化。假设我们有一个输入字符串“abcd”。在这里，我们遍历每个字符以找到它的长度，因此所花费的时间与字符串中的字符数成正比，例如 n 个字符。因此 O(n)。但是如果我们将字符串“abcd”的长度放在一个变量中，那么无论字符串有多长，我们仍然可以通过查看变量 len 来找到字符串的长度。(len = 4)。例如：返回 23。无论您输入什么，我们的输出仍然为 23。因此复杂度为 O(1)。因此，该程序将在输入大小的恒定时间内运行。对于 O(log n) - 操作以对数步长进行。

https://drive.google.com/file/d/0B7eUOnXKVyeERzdPUE8wYWFQZlk/view?usp=sharing

观察上面链接中的图像。在这里我们可以看到弯曲的线（对数线）。在这里，我们可以说，对于较小的输入，O(log n) 表示法效果很好，因为我们在弯曲线中可以看到所花费的时间更少，但是当输入增长时，线性表示法即 O(n) 被认为是更好的方法。还可以看到最好和最坏的情况。就像上面的例子。

你也可以参考这个作弊算法：http ://bigocheatsheet.com/

于 2014-12-14T20:34:01.197 回答
-1

为什么不尝试使用 Union-Find？您可以将每个音乐会日+接下来的 5 天分组为一组的一部分，然后在给定的日期执行 FIND，这将返回下一个集 ID，这将是您的下一个音乐会日期。

如果使用树实现，这会产生 O(log n) 时间复杂度。

于 2014-07-28T22:40:15.253 回答