How to know - will 2 eternal repeatable intervals overlap in the future (reopened)-CodePudding

In brief, I have:

startTime (When my interval chain will start)

repeatEveryMinuteInterval (Repeat every minute of this action)

duration (Duration of the action)

It builds the chain of the intervals. Example 1:

StartTime - 15:00 UTC 9/19/2022
repeatEveryMinuteInterval - 15
duration - 5 minutes

15:00 - 15:05
15:15 - 15:20
15:30 - 15:35
15:45 - 15:50
16:00 - 16:05
// as it is endless it will iterate an infinite number of times

Example 2:

StartTime - 03:07 UTC 10/19/2022
repeatEveryMinuteInterval - 30
duration - 5 minutes

03:07- 03:12
03:37- 03:12
04:07- 04:12
// as it is endless it will iterate an infinite number of times

My question is: as these 2 interval chains do not have an end, how can I know that they wouldn't overlap in the future?

I assume, that 2 intervals overlap if they share the same time even partially.

15:30 - 15:45
15:25 - 15:31 

They are overlapping as they both have 15:30 - 15:31 in the intervals.

From the implementation point of view, I have figured out 3 ways, and all of them are dummy )

1.) Assume post that they will overlap as it is an endless set and impossible to calculate and have a consistent result.

2.) To calculate maybe the next 1000 of the iterations and compare. The thing is that I don't know how many times should i iterate to have a valid result and for this operation not to take a lot of time to calculate.

UPD: If anyone has a solution with or without time zones, I will be glad to communicate. Thanks

I am reopening my question as a received update from the CryptoFool that this problem can be solved.

Closed question https://stackoverflow.com/questions/73768795/how-to-know-will-2-repeatable-intervals-overlap-in-the-future

Update 2: adding new examples (where repeatEveryMin >= duration)

StartTime - 00:00 UTC 9/20/2022
repeatEveryMinuteInterval - 600 (every 10 hours)
duration - 5 minutes

00:00 - 00:05
10:00 - 10:05
20:00 - 20:05
// other iterations

StartTime - 19:02 UTC 9/20/2022
repeatEveryMinuteInterval - 30
duration - 5 minutes

19:02 - 19:07
19:32 - 19:37
20:02 - 20:07
// other iterations

In this example, these 2 internals overlap here:`

interval 1: 20:00 - 20:05
interval 2: 20:02 - 20:07

CodePudding user response：

The answer to this problem comes from the notion of a least common multiple. No matter what the periods of the two sequences are, there will always be a point in time where they are both starting a new cycle at that same point in time, possibly with an offset. From that point on, everything that happens will be a repeat of what happened in that first cyce.

To get the length of this cycle, one just needs to find the least common multiple of the two repeat intervals. In the worst case, which occurs when one of the two intervals is a prime number, that period will be interval1 * interval2. If the numbers are not primes, any common factors that they share will mean that the cycle length will be reduced. Here's the Python function that will calculate the least common multiple:

def compute_lcm(a, b):
    return abs(a*b) // math.gcd(a, b)

If the two sequences started at the same time, everything would be pretty simple from here. But if the two intervals start at different times, things get more complicated. We basically have to allow for the fact that a single cycle won't capture all of both sequences, because one sequence might start a little before the single cycle starts, and another might end after the cycle starts.

I reasoned out what had to be done to take the offset of the two sequences into account, and also accounted for the duration possibly extending things out a bit. I might not have gotten this quite right. I've created a couple of examples, reasoned out by hand what the overlap would be, and then run those examples through my code and I got the same answers. So it should be correct.

So here it is in all its gory glory:

import math

def compute_lcm(a, b):
    return abs(a*b) // math.gcd(a, b)

# First sequence
# 15-20, 30-35, 45-50, 60-65
seq1 = {
    'start': 15,
    'repeat_interval': 15,
    'duration': 5,
    'extra': 0,
}

# Second sequence
# 5-11, 25-31, 45-51, 65-71
seq2 = {
    'start': 5,
    'repeat_interval': 20,
    'duration': 6,
    'extra': 0,
}

# Overlap by inspection: 30, 45-49

# Compute the magic value, the number of minutes at which the two sequences start over at the same time offset as for the initial cycle.
lcm = compute_lcm(seq1['repeat_interval'], seq2['repeat_interval'])

overall_start = 0

# This stuff's a bit crazy, I know.  Sorry.

# For whichever sequence starts last, add extra repeat intervals to
# the start of it so that it covers the entire main cycle, which
# starts where the other cycle starts.
if seq1['start'] > seq2['start']:
    while seq1['start'] > seq2['start']:
        seq1['start'] -= seq1['repeat_interval']
        seq1['extra']  = seq1['repeat_interval']
    overall_start = seq1['start']
else:
    while seq2['start'] > seq1['start']:
        seq2['start'] -= seq2['repeat_interval']
        seq2['extra']  = seq2['repeat_interval']
    overall_start = seq2['start']

# Compute a worst case length for the 'minutes' array we'll use
# to tally to find the overlaps.  
total_length = lcm   max(seq1['extra'], seq2['extra'])   max(seq1['duration'], seq2['duration'])
offset = -min(seq1['start'], seq2['start'])

# Create an array such that each element in the array represents a minute of time
minutes = [0] * total_length


# Now walk through each sequence from its start.  For each, compute each interval, and then loop over that
# interval, incrementing the value of each minute of it in the 'minutes' array to record that the sequence
# was "on" during that minute.
#
# NOTE: I chose to consider an interval's start and ent times to be exlusive of the last minute.  So the
# interval 10-15 consists of the minutes 10, 11, 12 and 13.  I could have gone the other way, including the
# last minute in each interval. If that's what is desired, I leave making that small change as an exercise for the OP

for seq in (seq1, seq2):
    t = seq['start']
    while t < seq['start']   lcm   seq['extra']:
        for o in range(seq['duration']):
            tt = offset   t   o
            minutes[tt]  = 1
        t  = seq['repeat_interval']

# At this point, overlaps consist of values in the 'minutes' array that have a value of 2, meaning
# that both sequences were "on" during that minute.  Walk through the array, printing out each
# minute that was part of an overlap
for i in range(total_length):
    if minutes[i] > 1:
        print(i-offset)

Result:

If you want to generate more of the overlap minutes, just keep iterating over more minute values, and do a mod on the minute value to do the lookup in the 'minutes' array. So:

count = minutes[m % lcm]

If count == 2, then minute 'm' was part of an overlap, for any value of 'm'.

Oh..one other thing, and maybe this is where my answer lost the green check. This answer doesn't account for times specified as hours and minutes. It just gives the answer to the basic idea of calculating overlaps and doing so for the minimum necessary cycle length, with all values represented in minutes. To do this for hours, or days, all one would have to do is convert the time values to a minutes-only representation. Time zones would also add complexity, but you'd just offset the minutes values to account for any time zone shift.