查找是否有规律的经常性时间间隔重叠的算法？

Question

有多个时间间隔，从startTime到endTime。每个间隔由重复的开始时间，结束时间（直到重复要继续的点），onDuration（当它处于活动状态并且可以重叠时）以及offDuration定义。

采样间隔：

startTime: 3 secs 
endTime: 30 secs 
onDuration: 3 secs (represented by x) 
offDuration: 5 secs (represented by -) 

|--[xxx]-----[xxx]-----[xxx]-----[xxx]-| 

重叠的间隔：两个重复系列被说成重叠，如果他们有重叠接通时间（x）的它们各自的开始和结束时间的范围内。

问题：有几十个这样的间隔。提供了一个新的重复间隔，由相同的参数（startTime，endTime，onDuration，offDuration）定义。在startTime和endTime的时间范围内，这个新的重复间隔是否与任何现有时间间隔重叠？

PotentialInterval：因为它结束它会重叠之前

startTime: 6 secs 
endTime: 15 secs 
onDuration: 3 secs 
offDuration: 6 secs 

PotentialInterval不SampleInterval冲突。

注意：

1. 这是非常相似的this question，但我不能完全理解解决方案的正确性。此外，我感兴趣的只是确定它们是否冲突（布尔真或假），而不是实际冲突的时间间隔。

2. 每个区间的结束时间和开始时间形成算术级数。 startTime _n = startTime +（n-1）（onDuration + offDuration）其中startTime _n < endTime。因此，也许this question可能指向正确的方向，但我无法找到一种方法来合并持续时间。

3. 样品要小得多。实际上，每次重复中的个体间隔的数量将是几千（例如从现在开始直到下一个10年，每天从下午3点到下午4点）。此外，重复次数可能是数百次。因此，对数据进行非规格化（列出每个事件的列表）可能并不实际。

4. 该数据存储在NoSQL数据库中，因此数据库中的日期 - 时间操作是不可能的。这需要在内存中完成，最好大约500毫秒

Answer 1

我不认为有一个简单的公式/算法来确定两个系列是否重叠。我会详细阐述一下。让s1 =系列1的startTime，a1 = onDuration，b1 = offDuration，e1 = endTime，并且c1 = a1 + b1。让我们也有类似于series2的s2，a2，b2，c2和e2。问题是，系列的开启期是否重叠？设i1表示系列1的特定周期，i1> = 0，i1 = < = floor（（e1-k1）/ c1）= m1。 （我忽略了这个系列的正确尾巴，但是这些可以分开处理。）同样适用于i2。

接下来的问题是，我们可以找到整数i1和i2，使得区间[s1 + i1 * c1，s1 + i1 * c1 + a1]和[s2 + i2 * c2，s2 + i2 * c2 + a2 ] 交叠？正如m69所示，这相当于检查是否

abs((s1+2*i1*c1+a1)/2 - (s2+2*i2*c2+a2)/2) < (a1+a2)/2 

我们有两种可能性，模数下的表达式为正数或负数。假设这是肯定的，那么我们有

0 <= i1 <= m1 
0 <= i2 <= m2 
s1+2*i1*c1+a1 >= s2+2*i2*c2+a2, 
s1+2*i1*c1+a1 - (s2+2*i2*c2+a2) < a1 + a2 

或者，

0 <= i1 <= m1 
0 <= i2 <= m2 
i1 >= c2/c1*i2 + (s2-s1+a2-a1)/(2*c1) 
i1 < c2/c1*i2 + (2*a2+s2-s1)/(2*c1) 

（但愿我没有做过任何代数愚蠢的错误）。假设模数下的表达式为负数，我们得到另一个系统。

这是一个可能非空的多边形，最多有六面。问题是，是否有任何整数值落在里面？这是一个丢番图线性不等式问题。如果谷歌它，你回来姊妹网站:)

https://mathoverflow.net/questions/69966/algorithm-for-solving-systems-of-linear-diophantine-inequalities