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

Question

有多个重复出现的时间间隔，从 startTime 到 endTime。每个间隔由循环的开始时间、结束时间(直到循环将继续的时间点)、onDuration(当它处于 Activity 状态并且可以重叠时)和 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 的时间范围内，这个新的循环间隔是否与任何现有间隔重叠？

潜在区间:

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

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

注意事项:

1. 这与 this question 非常相似，但我无法完全理解解决方案的正确性。此外，我只对确定它们是否冲突( boolean 值 true 或 false)感兴趣，而不是实际的冲突间隔。

2. 每个区间的结束时间和开始时间都是等差数列。 startTime_n = startTime + (n-1) (onDuration + offDuration) 其中 startTime_n < endTime。因此，也许 this question可能指向正确的方向，尽管我找不到将持续时间纳入其中的方法。

3. 样本要小得多。实际上，每次重复中的单独间隔数将是数千个(例如，从现在到 future 10 年的每一天，从下午 3 点到下午 4 点)。此外，重复的次数可能有数百次。因此，对数据进行反规范化(列出每次出现的事件)可能不切实际。

4. 此数据存储在 NoSQL 数据库中，因此无法在数据库中进行日期时间操作。这需要在内存中完成，最好在 ~500 毫秒的数量级

Answer 1

我不认为有一个简单的公式/算法可以确定两个系列是否重叠。我会详细说明一下。设 s1 = 系列 1 的开始时间，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