查找定期重复出现的时间间隔是否相互重叠的算法？

Question

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

采样间隔：

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的时间范围内，此新的重复间隔是否与任何现有间隔重叠？

潜在区间：

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

PotentialInterval与SampleInterval不冲突，因为它在重叠之前结束。

笔记：

>

这与这个问题非常相似，但我无法完全理解解决方案的正确性。此外，我感兴趣的只是确定它们是否冲突（布尔值true或false），而不是实际的冲突间隔。

每个间隔的结束时间和开始时间都构成一个算术级数。开始时间_n=开始时间（n-1）（持续时间），其中开始时间_n

样本要小得多。事实上，每次复发的个体间隔数将为数千（例如，从现在到未来10年，每天下午3点到4点）。而且，复发的数量可能是数百。因此，对数据进行非规范化（列出每次发生的情况）可能不可行。

此数据存储在非关系型数据库中，因此不可能在数据库中进行日期时间操作。这需要在内存中完成，并且最好在〜500毫秒的数量级

Answer 1

我不认为有一个简单的公式/算法来确定两个序列是否重叠。我会详细说明一下。设s1=系列1的开始时间，a1=持续时间，b1=关闭持续时间，e1=结束时间，c1=a1 b1。让我们也有s2，a2，b2，c2和e2类似的序列2。问题是，序列的on周期是否重叠？

设i1表示系列1的特定周期，i1

那么问题是，我们能否找到整数i1和i2，使得区间[s1i1*c1，s1i1*c1a1]和[s2 i2*c2，s2 i2*c2a2]重叠？如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