查找定期重复时间间隔是否彼此重叠的算法？

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  

潜在间隔与样本间隔不冲突，因为它在可能重叠之前就结束了。

备注：

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

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

3. 样本要小得多。实际上，每个重复中的单个间隔数量可能会有几千个（例如，从现在到未来10年每天下午3点到4点）。此外，重复次数可能会达到数百次。因此，去规范化数据（制作每个发生的列表）可能不太实用。

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

- user1271286

---

有点像作业... - dat3450

你有什么问题？ - Dawood ibn Kareem

@dat3450：这不是作业，而是我目前为资源调度工作的问题。虽然我希望我曾经做过这种作业，这样我现在就不会卡住了 :) - user1271286

@DawoodibnKareem：我已将“任务”更名为“问题”。我的问题是要找出给定的新循环是否与给定时间范围内的任何现有循环间隔重叠。（注意＃1也或多或少谈到了同样的问题，只是我的问题需要一个布尔值来判断是否重叠，而那里的OP则期望实际重叠） - user1271286

你能够逐步解决它吗？1.丢弃所有完全在前或在后的复合区间。2.在剩下的区间中，检查哪些区间具有相同的周期（开+关持续时间）。如果周期相同，则只需检查如何相对偏移。3.现在留下的复合区间有不同的周期，这意味着它们最终会相交。您可以计算周期的最小公倍数。如果它比一般重叠小，将存在开启持续时间的重叠。4.剩下的可能很适合非规范化处理。 - Andrei

Answer 1

我认为没有一个简单的公式/算法可以确定两个系列是否重叠。我稍微解释一下。假设s1是系列1的开始时间，a1是开启持续时间，b1是关闭持续时间，e1是结束时间，c1是a1 + b1。同样地，我们也有s2、a2、b2、c2和e2来表示系列2。问题是，这些系列的开启期是否重叠？

让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

- Andrei