Search algorithm if regular repeating time intervals overlap with each other?
There are several repeating time intervals from startTime to endTime. Each interval is defined by the start time of the repetition, the end time (until the repetition continues), onDuration (when it is active and may overlap), and offDuration.
Interval example :
startTime: 3 secs
endTime: 30 secs
onDuration: 3 secs (represented by x)
offDuration: 5 secs (represented by -)
|--[xxx]-----[xxx]-----[xxx]-----[xxx]-|
Overlap intervals . Two repeating series are said to overlap if they overlap in time (x) within the start and end time intervals of each.
Question : There are dozens of such intervals. A new repeating interval is provided, defined with the same parameters (startTime, endTime, onDuration, offDuration). Does this new repeating interval overlap with any of the existing intervals, within the 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 overlaps.
Notes :
-
It is very similar to this question , but I could not fully understand the correctness of the solution. Also, I'm only interested in determining if they are in conflict (boolean true or false), not the actual conflict interval.
-
Both the end time and the start time of each interval form an arithmetic progression. startTime n= startTime + (n-1) (onDuration + offDuration), where startTime n<end time. So maybe this question can point in the right direction, although I couldn't find a way to include durations in it.
-
The samples are much smaller. In fact, the number of individual intervals in each repetition will be several thousand (for example, from now to the next 10 years every day from 3 pm to 4 pm). In addition, the number of repetitions can be hundreds. Thus, denormalizing the data (listing each of them) may not be practical.
-
This data is stored in a NoSQL database, so manipulation of dates in the database is not possible. This needs to be done in memory and preferably at ~ 500 milliseconds
source to share
I don't think there is a simple formula / algorithm to determine if two series overlap. I'll clarify a little. Let s1 = startTime from series 1, a1 = onDuration, b1 = offDuration, e1 = endTime and c1 = a1 + b1. Similarly, we will have s2, a2, b2, c2 and e2 for series 2. The question is, do the overlapping periods of the series overlap?
Let i1 denote a particular period of row 1, i1> = 0, i1 <= floor ((e1-k1) / c1) = m1. (I'm ignoring the correct series tails, but they can be handled separately.) Likewise for i2.
Then the question arises: can we find an integer i1 and i2 such that the intervals [s1 + i1 * c1, s1 + i1 * c1 + a1] and [s2 + i2 * c2, s2 + i2 * c2 + a2] intersect? As m69 suggests, this is equivalent to checking that
abs((s1+2*i1*c1+a1)/2 - (s2+2*i2*c2+a2)/2) < (a1+a2)/2
We have two possibilities: either the modulus expression is positive or 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)
(I hope I didn't make any stupid mistakes in algebra). We get another system, which assumes that the modulus expression is negative.
It is a possibly non-empty polygon with at most six sides. The question is, are there any integer values getting inside? This is the problem of Diophantine linear inequalities. If you go to Google you will be taken back to the sister site :)
source to share