查找包含给定时间瞬间的时间间隔

Question

我试图解决以下问题：给定N个时间间隔，每个时间间隔指定为（开始，结束），不重叠，根据开始排序——找到一个包含给定日期的时间间隔。例如：

[1,4] [5,8] [9,10][11,20]

3人进入第一节，15人进入第四节，以此类推。

到目前为止，我有以下基本想法：

1. 我们可以使用二进制搜索来找到相应的间隔（logn）
2. 由于可能只有少数时间间隔较大，其余时间间隔较小，因此根据时间长短对itervals进行排序可能是值得的。然后，在统计上，大多数情况下，我们会“命中”最长的间隔（O（1）），只是有时这会导致最坏情况的复杂性为N

我在想，这两种方法是否有结合的余地。另一个想法是根据持续时间进行排序，并将所有间隔插入到树中，通过开始日期进行比较，这在最坏的情况下，当最长持续时间按时间顺序排列时，这种方法的性能相当于2。

我设想的理想解决方案是有一棵树（或一些类似的数据结构），树的顶部包含最长的间隔，然后两个分支将有接下来的两个最长间隔等。然而，我认为没有办法在树中分支，也就是说，因为我们明确假设我们根据长度插入，我们不能真正抛弃树的左边或右边。

如有任何评论，将不胜感激。

Answer 1

把两者结合起来是可能的。这是我的想法，

建立一个基于范围长度的二叉树，假设我们有以下范围，

a:[0,1]、b:[1,2]、c:[3,10]、d:[11,12]、e:[13,14]

我们从底部建造树，我们根据范围大小组合叶子，所以第一轮我们可以得到内部叶子，

（a，b），c，（d，e）

然后

（a、b、c）、（d、e）

根将是，

（a、b、c、d、e）

在每一轮中，我们将范围长度最小的节点组合在一起，保持树的深度。

每个节点指向左、右子节点，并保持子节点的最小、最大值。

如有不妥，请指出。

Answer 2

您可以在二叉搜索树中对某些节点进行优先级排序，并保持其平衡：

从你的组合方法开始（将更长的间隔放在更靠近顶部的位置），并采用一系列轮换来平衡二叉搜索树（在打破一些优先级的同时，如果没有打破平衡，它应该保留靠近根的高优先级节点）。

要平衡一棵树，试试这个策略（未经测试）：

• 平衡左半部分（根的子树）
• 平衡右半部分
• 如果右半部分高于左半部分1（AVL平衡条件
  • 虽然这是真的
    • 如果左右四分之一（右半部分的左半部分）高于右四分之一，则向右旋转右子树（开始AVL双旋转）
    • 向左旋转树（完成AVL旋转）
    • 平衡左半部分（两个左四分之一已经平衡-从#3开始）
    • 做另一种情况的相反

    这应该产生一个AVL平衡树，尽可能尊重原始优先级。

Answer 3

这两种方法的简单组合在大多数情况下提供了一个O（1），在最坏的情况下提供了O（logN），但大O符号中的隐藏常数将是两倍：

1. 将原始数组设为间隔
2. 按照建议，创建第二个数组，按间隔长度降序排序。让它成为长度
3. 对于每个查询，使用二进制搜索在间隔中进行搜索，使用线性搜索在长度中进行搜索。搜索将并行进行¹，第一个搜索完成后，另一个搜索也将停止

因为在步骤3中，我们可以在间隔中执行多达c*log（n）的二进制搜索步骤，我们总共将执行多达2*c*log（n）的步骤。如果在<代码>长度<代码>中找到元素更快，它将导致二进制搜索在中间结束，并且我们将得到减少的操作数，（但具有双常数，然后是原来的方法）。

（1）不需要并行计算机，可以通过在每个步骤中搜索一个步骤来实现，在单个线程上模拟并行计算，直到找到答案。（一般信息，不需要理解答案：“并行搜索”的概念是由伊文、伊泰和沙米尔在他们的文章《时间表的复杂性和多商品流动问题》中介绍的）