根据开始时间排序的给定间隔集。在 O(logn) 中计算其中包含 Time "T" 的所有间隔
Given set of intervals sorted according to Start time. Count all the intervals which has Time "T" in them in O(logn)
假设区间列表可能是[[1,3],[2,4],[6,12]]并且查询时间T = 3。上面列表中有3个区间的数量是 2（即）[[1,3],[2,4]]。是否可以在 O(logn) 时间内完成此操作？
嗯，需要注意的一点是，对于包含T的区间，其开始时间必须小于或等于T。由于这些是按开始时间排序的，因此可以使用基本的二分查找来消除所有在 O(log n) 时间内开始太晚的那些。
如果我们可以假设这些也按结束时间排序——也就是说，没有区间完全包含前一个区间——那么你可以使用另一个二分搜索来消除所有结束时间在 T 之前的区间。这将使 运行 时间保持在 O(log n) 中。
如果我们不能做出那个假设，事情就会变得更复杂，我想不出比 O(n log n) 更好的方法[通过按结束时间对剩余列表进行排序并执行另一个二进制搜索]。也许有办法？
EDIT 正如Qbyte下面所说，最后的排序是多余的；您可以通过对剩余集合进行简单的线性搜索将其降低到 O(n)。话又说回来，如果你无论如何都要使用 O(n) 解决方案，你也可以跳过整个算法，只对原始集进行线性搜索。
让我们假设间隔按开始时间排序。二进制搜索 O(log n) 将消除不能包含 T 的区间。剩下的可能.
假设结束时间未排序 (OP)
你必须扫描剩下的，O(n)，计算它们。总复杂度 O(n)。鉴于此，您还不如从不进行二进制搜索而只是扫描整个列表。
假设结束时间也已排序
如果剩下的也按结束时间排序，可以再做一次二分查找，复杂度保持在O(log n).
但是你还没有完成。你需要计数。
您知道开始的次数。如果你不这样做，你就不能进行二进制搜索。您将知道每个二进制搜索的最后测试的索引。从这里开始，它是一个 O(1) 计算选项。
因此，此选项的总复杂度为 O(log n)。
这在一般情况下无法在 O(log n) 时间内完成。
您可以对开始时间进行二进制搜索以找到可能包含查询时间的最后一个间隔，但由于结束时间没有隐含的顺序，因此您必须从列表的开始顺序搜索到项目您确定为最后一个确定查询时间是否在任何这些间隔内。
考虑，例如，[(1,7),(2,11),(3,8),(4,5),(6,10),(7,9)]，查询时间为 7。
开始时间的二分查找会告诉你所有的间隔可能包含查询时间。但是因为结束时间没有任何特定的顺序，所以你不能对它们进行二分查找。您必须查看每个单独的时间间隔以确定结束时间是否大于或等于查询时间。在这里，您看到 (4,5) 不包含查询时间。
假设区间列表可能是[[1,3],[2,4],[6,12]]并且查询时间T = 3。上面列表中有3个区间的数量是 2（即）[[1,3],[2,4]]。是否可以在 O(logn) 时间内完成此操作？
嗯，需要注意的一点是，对于包含T的区间，其开始时间必须小于或等于T。由于这些是按开始时间排序的，因此可以使用基本的二分查找来消除所有在 O(log n) 时间内开始太晚的那些。
如果我们可以假设这些也按结束时间排序——也就是说，没有区间完全包含前一个区间——那么你可以使用另一个二分搜索来消除所有结束时间在 T 之前的区间。这将使 运行 时间保持在 O(log n) 中。
如果我们不能做出那个假设，事情就会变得更复杂，我想不出比 O(n log n) 更好的方法[通过按结束时间对剩余列表进行排序并执行另一个二进制搜索]。也许有办法？
EDIT 正如Qbyte下面所说，最后的排序是多余的；您可以通过对剩余集合进行简单的线性搜索将其降低到 O(n)。话又说回来，如果你无论如何都要使用 O(n) 解决方案，你也可以跳过整个算法，只对原始集进行线性搜索。
让我们假设间隔按开始时间排序。二进制搜索 O(log n) 将消除不能包含 T 的区间。剩下的可能.
假设结束时间未排序 (OP)
你必须扫描剩下的，O(n)，计算它们。总复杂度 O(n)。鉴于此，您还不如从不进行二进制搜索而只是扫描整个列表。
假设结束时间也已排序
如果剩下的也按结束时间排序，可以再做一次二分查找，复杂度保持在O(log n).
但是你还没有完成。你需要计数。
您知道开始的次数。如果你不这样做，你就不能进行二进制搜索。您将知道每个二进制搜索的最后测试的索引。从这里开始，它是一个 O(1) 计算选项。
因此，此选项的总复杂度为 O(log n)。
这在一般情况下无法在 O(log n) 时间内完成。
您可以对开始时间进行二进制搜索以找到可能包含查询时间的最后一个间隔，但由于结束时间没有隐含的顺序，因此您必须从列表的开始顺序搜索到项目您确定为最后一个确定查询时间是否在任何这些间隔内。
考虑，例如，[(1,7),(2,11),(3,8),(4,5),(6,10),(7,9)]，查询时间为 7。
开始时间的二分查找会告诉你所有的间隔可能包含查询时间。但是因为结束时间没有任何特定的顺序，所以你不能对它们进行二分查找。您必须查看每个单独的时间间隔以确定结束时间是否大于或等于查询时间。在这里，您看到 (4,5) 不包含查询时间。