There are multiple recurring intervals of time, starting from a startTime to an endTime. Each interval is defined by the start time of the recurrence, the end time (till the point where the recurrence is going to continue), the onDuration (when it is active, and can overlap), and the offDuration.
Sample Interval:
startTime: 3 secs
endTime: 30 secs
onDuration: 3 secs (represented by x)
offDuration: 5 secs (represented by -)
|--[xxx]-----[xxx]-----[xxx]-----[xxx]-|
Overlapping Intervals: Two recurring series are said to overlap if they have overlapping on-times (x) within the start and end time ranges of each of them.
Question: There are tens of such intervals. A new recurring interval, defined by the same parameters (startTime, endTime, onDuration, offDuration) is provided. Does this new recurring interval overlap with any of the existing intervals, within the time ranges of startTime and endTime?
PotentialInterval:
startTime: 6 secs
endTime: 15 secs
onDuration: 3 secs
offDuration: 6 secs
PotentialInterval does not conflict with SampleInterval because it ends before it would have overlapped.
Notes:
This is very similar to this question, but I couldn't completely understand the correctness of the solution. Also, I'm interested in only determining whether they conflict (boolean true or false), rather than the actual conflicting interval.
Both the end time and start time of each interval form an arithmetic progression. startTimen = startTime + (n-1) (onDuration + offDuration) where startTimen < endTime. Thus, maybe this question might point in the right direction, though I couldn't find a way to incorporate durations in this.
The samples are much smaller. In reality, the number of individual intervals in each recurrence would be several thousands (for eg, from now till next 10 years every day from 3PM to 4PM). Also, the number of recurrences could be hundreds. Thus, denormalizing the data (making a list of each occurence) may not be practical.
This data is stored in a NoSQL database, so date-time manipulations within the database are not possible. This needs to be done in memory, and preferably in the order of ~500 milliseconds
I do not think there is a simple formula / algorithm to determine whether two series overlap. I will elaborate a bit. Let s1 = startTime of series 1, a1 = onDuration, b1 = offDuration, e1 = endTime, and c1 = a1 + b1. Let us also have s2, a2, b2, c2, and e2 similarly for series2. The question is, do the on periods of the series overlap?
Let i1 denote a particular period of series 1, i1 >= 0, i1 <= floor((e1-k1)/c1) = m1. (I ignore the right tails of the series, but those can be handled separately.) Similarly for i2.
The question then is, can we find integer i1 and i2 such that the intervals [s1+i1*c1, s1+i1*c1+a1] and [s2+i2*c2, s2+i2*c2+a2] overlap? As m69 suggests, that is equivalent to checking whether
abs((s1+2*i1*c1+a1)/2 - (s2+2*i2*c2+a2)/2) < (a1+a2)/2
We have two possibilities, either the expression under the modulus is positive or it is negative. Suppose it is positive, then we have
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
Or,
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)
(Hopefully, I have not done any silly mistakes in algebra). We get another system assuming that the expression under the modulus is negative.
This is a possibly non-empty polygon with at most six sides. The question is, do any integer values fall inside? That is a diophantine linear inequalities problem. If you google it, you come back to a sister site :)