我正在尝试解决以下问题:给定 N 个时间间隔，每个时间间隔指定为(开始，结束)，不重叠，根据开始排序 - 找到包含给定日期的间隔。例如给出:
[1,4] [5,8] [9,10][11,20]
3 属于第一个间隔，15 属于第四个间隔等
到目前为止，我有以下基本想法:
- 我们可以使用二进制搜索找到对应的区间(Log N)
- 由于可能只有少数间隔较大，而其余间隔较小，因此根据持续时间对迭代进行排序可能是值得的。然后，在统计上，大多数时候我们会“命中”最长的间隔 (O(1))，只是有时这会导致 N 的最坏情况复杂度。
我在考虑是否可以将这两种方法结合起来。另一个想法是根据持续时间排序并将所有间隔插入树中，并按开始日期进行比较，这在最坏情况下最长持续时间按时间顺序排列时，这种方法的性能等于 2。
我想象的理想解决方案是有一棵树(或一些类似的数据结构)在顶部包含最长的间隔，然后两个分支将有接下来的两个最长的间隔等。但是，我看不出办法在那棵树中分支，即因为我们明确假设我们根据长度插入，所以我们不能真正丢弃树的左侧或右侧。
如有任何意见，我们将不胜感激。
最佳答案
这两种方法的简单组合在大多数情况下提供了 O(1)，在最坏的情况下提供了 O(logN)，但是大 O 中的隐藏常量符号将是双重的:
- 让原数组为
intervals - 创建第二个数组，按照建议的间隔长度降序排列。让它成为
长度 - 对于每个查询，使用二进制搜索在
intervals中搜索，并使用线性搜索在lengths中搜索。搜索将并行1 完成，第一个完成的搜索也会导致另一个停止。
因为在第 3 步中，我们可能会在 intervals 中执行最多 c*log(n) 步的二分查找，我们将最多执行 2* c*log(n) 总体步骤。如果我们在 lengths 中更快地找到元素，它会导致二分查找在中间结束，并且我们会减少操作次数(但使用 double 常量然后是原始方法)。
(1)不需要并行计算机，一步一步搜索，模拟单线程并行计算，直到找到答案。 (一般信息，理解答案不需要:S.Even、A.Itai 和 A.Shamir 在他们的文章 On the Complexity of TimeTable and Multi Commodity Flow Problems 中介绍了“并行搜索”的概念)
关于java - 查找包含给定时刻的间隔，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14019544/