查找范围列表(一个或多个)的所有子范围

Question

>我有一些文件在开始时间和结束时间之间写入，如下所示;

[0 , 1] , [1,2] , [2 , 3] , [3, 4] , [4, 7] , [7, 8]

我想用 O(N( 找到 2 到 5 之间的所有子范围;
对于上面的例子：

[1,2] , [2 , 3] , [3, 4] , [4, 7]

如果我写如下条件，这有效

if (StartTime >= 2 and StartTime <= 5) or (EndTime >=2 and EndTime <= 5)
add this to your list of sub ranges

但是如果我有一个范围，这将失败：

[0,8] 

我正在搜索 2 到 5 之间的文件

谁能建议如何做到这一点？

Answer 1

请注意，如果出现以下情况，间隔 A 和 B 重叠

(A.Start <= B.End) and (B.Start <= A.End)

例：

A = [2,5]
B = [0,8]
(A.Start <= B.End) and (B.Start <= A.End)
(2<=8) and (0<=5)  is True, so they overlap

附言在一般情况下，值得使用专用数据结构(如间隔树(来实现更好的渐近时间。

Answer 2

在这里：

if(startTime<=5 && endTime>=2);

或

if(max(startTime,2)<=min(endTime,5));

这将在所有条件下工作。