如何检查两个日期系列是否重叠并确定它出现的第一个日期？

Question

如何检查两个日期系列是否重叠并确定它出现的第一个日期？

假设我在 Google 日历中创建了两个事件。其中一个在 Date1 中并且每 X 天重复一次；另一个在 Date2 中，每 Y 天重复一次。

确定这两个系列是否会在某天重叠并找到它会发生的第一个日期的最佳算法是什么？

示例 1：

Date1 = Feb-15, 2016
X = 14 (repeat every 14 days)
Date2 = Feb-22, 2016
Y = 21 (repeat every 21 days)
Result: first overlap on Mar-14, 2016

示例 2：

Date1 = Feb-15, 2016
X = 14 (repeat every 14 days)
Date2 = Feb-22, 2016
Y = 28 (repeat every 28 days)
Result: will never overlap

Answer 1

让我们定义两个系列之间的数学关系。首先定义一些变量：

c - This is the initial offset between the starting dates (Date2 - Date1)

S₁ - This is the "step size" (repeat) of Date1.

S₂ - This is the "step size" (repeat) of Date2.

i - This repetition count of series 1 at point of overlap.

j - This repetition count of series 2 at point of overlap.

我们可以说当级数重叠时，存在一些i，j∈ℤ（整数）使得：

i*S₁ = c + j*S₂ (and then)
i = (c + j*S₂) / S₁

找到j（然后重叠点通过c + j*S₂), 我们可以使用如下算法:

if c % S1 is 0 then return 0
else  
  let j = 1
  while (S2 * j) % S1 != c
    if (c + S2 * j) % S1 == 0 then return j
    j = j + 1
  loop
  return -1 (not found)

如果算法 returns -1，则没有重叠。否则发现重叠。

您可以在这里尝试一下：

$('#find').click(function() {
  var c = +$('#C').val();
  var S1 = +$('#S1').val();
  var S2 = +$('#S2').val();

  var j = findOverlap(c, S1, S2);
  if(j === -1) {
    $('#result').text('No overlap!');
    return;
  }

  $('#result').text('Overlap found at ' + (c + S2 * j));
});

function findOverlap(c, S1, S2) {
  if(c % S1 === 0) {
    return 0;
  }

  var j = 1;
  while((S2 * j) % S1 > 0) {
    if((c + S2 * j) % S1 === 0) {
      return j;
    }
    j++;
  }
  return -1;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
C: <input type="text" id="C" /><br/>
S1: <input type="text" id="S1" /><br/>
S2: <input type="text" id="S2" /><br/>
<button id="find">Find!</button><span id="result"></span>

我想还有一种纯数学方法可以解决这个问题，但我认为它会涉及 LCM 算法的变体，这将需要类似的迭代步骤。

如何检查两个日期系列是否重叠并确定它出现的第一个日期？

How to check if two series of dates overlap and determine the first date that it occurs?

performance

date

comparison

range