我正在尝试解决以下问题：给定N个时间区间，每个区间都指定为（开始时间，结束时间），不重叠，并按照开始时间排序 - 找到包含给定日期的区间。例如，给定：
[1,4] [5,8] [9,10][11,20]
3落入第一个区间，15落入第四个区间等。
到目前为止我有以下基本想法：
我在考虑是否有结合这两种方法的空间。另一个想法是根据持续时间排序并将所有区间插入树中，比较开始日期。在最坏的情况下，当最长的持续时间按时间顺序排列时，这种方法和2的性能相同。
我想象中的理想解决方案是拥有一个树（或类似的数据结构），其中包含最长的区间，然后两个分支就会有接下来的两个最长的区间等等。然而，我看不到在该树中分支的方法，即由于我们根据长度进行显式假设，因此我们无法真正丢弃树的左侧或右侧。
任何评论都将不胜感激。
O(1)，最坏情况下为 O(logN)，但是在大 O 表示法中隐藏的常数将会翻倍：
intervalslengthsintervals 和线性搜索在 lengths 中进行搜索。搜索将同时进行1，第一个完成的 - 也会导致另一个停止。因为在步骤 3 中，我们可能在 intervals 中做高达 c*log(n) 步的二分查找，因此我们总共最多会做高达 2*c*log(n) 步。如果我们在 lengths 中更快地找到元素，它将导致二分搜索在中途结束，并且我们将获得减少的操作次数（但是常数会翻倍）。
(1) 不需要并行计算机，可以通过在每个步骤中搜索来实现，在单个线程上模拟并行计算，直到找到答案。（一般信息，不需要理解答案：S.Even、A.Itai和A.Shamir在他们的文章On the Complexity of TimeTable and Multi Commodity Flow Problems中介绍了“并行搜索”的概念）
2n + 1; 2n + 2索引）具有高缓存效率。 - John Dvorak我使用JodaTime和TimeSlots实现了类似的功能（几乎等同于Joda Period）。 Period是我的自定义类，具有DateTime类型的开始和结束时间。 我持有一个按结束日期排序的Periods TreeSet。
TimeSlot类：
public class TimeSlot<T> {
private DateTime start;
private DateTime end;
// accessors
...
}
实用方法：
public TimeSlot<T> getTimeSlot(DateTime pointInTime) {
for (TimeSlot<T> ts : getCounterTimeSlotSet()) {
if (ts.getPeriod().isDateInRange(pointInTime)) {
return ts;
}
}
return null;
}
public boolean isDateInRange(DateTime date) {
if (date == null) {
return false;
}
return date.isAfter(this.start.minusMillis(1))
&& date.isBefore(this.end.plusMillis(1));
}
你可能是对的，二分查找在这种奇怪的分布下不是最优的。尽管如此，当N = 10亿时，log_2(N)只有大约30。
如果要搜索的列表中的每个元素具有相等的可能性，则元素的二分查找是最优的。
因此，在这里使用多级二分查找可能是理想的，其中每个级别中的间隔大小大致相同。使用给定的示例：
First Level: [1-10] [11-20] # Size = 10
Second Level: [1-10] = [1,4] [5,8] [9,10] # Size = 4
如果在11到20之间，则完成，否则扩展[1-10]并检查间隔[1,4] [5,8] [9,10]。
设置搜索结构的额外成本考虑O（N log（N））以上，并且对于小间隔来说更加昂贵，但是如果最大间隔大小和最小间隔之间有足够大的差距，则平均搜索时间应该相当不错。
在最坏的情况下，您将拥有log（N）级别。
可能可以将两个结合在一起。这是我的想法，
根据范围长度构建二叉树，假设我们有以下范围，
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)
在每一轮中，我们组合范围长度最小的节点，记住树的深度。
每个节点指向左、右子节点，并保留子节点的最小值和最大值。
如果有任何错误，请指出。