java - 检查将来是否有 2 个可重复的永恒间隔重叠

Question

简而言之，我有:

startTime (When my interval chain will start)

repeatEveryMinuteInterval (Repeat every minute of this action)

duration (Duration of the action)

它构建了区间链。示例 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

示例 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

我的问题是:由于这 2 个区间链没有终点，我怎么知道它们将来不会重叠？

我假设，如果 2 个时间间隔甚至部分共享相同的时间，则它们会重叠。

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

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

从实现的角度，我想出了3种方式，而且都是dummy )

1.) 假设它们会重叠，因为它是一个无穷无尽的集合，无法计算并得到一致的结果。

2.) 计算下一个 1000 次迭代并进行比较。问题是我不知道我应该迭代多少次才能得到有效结果，并且这个操作不会花费很多时间来计算。

UPD:如果有人有带或不带时区的解决方案，我很乐意交流。谢谢

我重新打开我的问题，因为从 CryptoFool 收到了这个问题可以解决的更新。

关闭问题 https://stackoverflow.com/questions/73768795/how-to-know-will-2-repeatable-intervals-overlap-in-the-future

更新 2:添加新示例(其中 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

在这个例子中，这两个内部结构在这里重叠:`

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

Answer 1

这个问题的答案来自最小公倍数的概念。无论两个序列的周期是多少，总会有一个时间点，它们都在同一时间点开始一个新的循环，可能有一个偏移量。从那时起，发生的一切都将重复第一个周期中发生的事情。

要获得此循环的长度，只需找到两个重复间隔的最小公倍数即可。在最坏的情况下，即两个区间之一为质数时，该周期将为 interval1 * interval2。如果数字不是质数，则它们共享的任何公共(public)因子都将意味着循环长度将减少。下面是将计算最小公倍数的 Python 函数:

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

如果这两个序列同时开始，那么从这里开始一切都会变得非常简单。但如果这两个间隔在不同的时间开始，事情就会变得更加复杂。我们基本上必须考虑到这样一个事实，即单个循环不会捕获所有两个序列，因为一个序列可能在单个循环开始之前开始一点，而另一个可能在循环开始之后结束。

我推断出必须采取什么措施来考虑两个序列的偏移量，并且还考虑了可能会延长一些时间的持续时间。我可能没有完全正确地理解这一点。我已经创建了几个示例，手动推断出重叠是什么，然后通过我的代码运行这些示例，我得到了相同的答案。所以应该是正确的。

所以这里是它所有的荣耀:

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)

结果:

30
45
46
47
48
49

如果您想生成更多的重叠分钟数，只需继续迭代更多的分钟值，并对分钟值进行修改以在“分钟”数组中进行查找。所以:

count = minutes[m % lcm]

如果计数 == 2，则分钟 'm' 是重叠的一部分，对于 'm' 的任何值。

哦..还有一件事，也许这就是我的回答丢失了绿色勾号的地方。此答案不考虑指定为小时和分钟的时间。它只是给出了计算重叠的基本思想的答案，并为最小的必要周期长度这样做，所有值都以分钟表示。要在几个小时或几天内执行此操作，所有需要做的就是将时间值转换为仅分钟的表示形式。时区也会增加复杂性，但您只需抵消分钟值即可考虑任何时区变化。