假设区间列表可能是 [[1,3],[2,4],[6,12]] 并且查询时间 T = 3。上面列表中有 3 的区间数是 2 (即)[[1,3],[2,4]]。是否可以在 O(logn) 时间内完成？
最佳答案
在一般情况下，这不能在 O(log n) 时间内完成。
您可以对开始时间进行二分搜索以找到可能包含查询时间的最后一个间隔，但是由于结束时间没有隐含的顺序，您必须从列表的开始顺序搜索到您确定的项目作为最后一个确定查询时间是否在任何这些间隔内。
例如，考虑 [(1,7),(2,11),(3,8),(4,5),(6,10),(7,9)]，查询时间为7.
开始时间的二分查找会告诉您所有的间隔可能都包含查询时间。但是因为结束时间没有任何特定的顺序，所以你不能对它们进行二分查找。您必须查看每个单独的时间间隔以确定结束时间是否大于或等于查询时间。在这里，您看到 (4,5) 不包含查询时间。
关于algorithm - 根据开始时间排序的给定间隔集。在 O(logn) 中计算其中包含时间 "T"的所有间隔，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53990224/