如何检查两个日期系列是否重叠并确定它出现的第一个日期？ [英] How to check if two series of dates overlap and determine the first date that it occurs?

问题描述

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

想象一下我创建了两个日期Google日历中的活动。 Date1中的其中之一，每X天重复一次；

Imagine that I've created two events in Google Calendar. One of them in Date1 and repeating every X days; the other in Date2 and repeating every Y days.

确定两个序列是否有一天重叠并找到其发生的第一个日期的最佳算法是什么？ ？

What would be the best algorithm to determine if the two series will overlap someday, and find the first date that it would happen?

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

推荐答案

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

Lets define the mathematical relationship between the 2 series. First define some variables:

• c -这是开始日期（日期2-日期1）之间的初始偏移量


• S ₁
strong>-这是Date1的步长（重复）。

• S ₂ -这是Date2的步长（重复）。


• i -系列1的重复计数


• j -系列2在重叠点的重复计数。

• 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 ∈ℤ（整数）使得：

We can say that when the series overlap, there exists some i, j ∈ℤ (integers) such that:

i * S ₁ = c + j * S ₂ （然后）

i =（c + j * S ₂ ）/ S ₁

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

要找到 j （然后用 C + j * S ₂ ），我们可以使用以下算法：

To find j (and then the overlap point by c + j*S₂), we can use the following algorithm:

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)

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

If the algorithm returns -1, there's no overlap. Otherwise the overlap is found.

您可以在此处尝试：

$('#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算法的一种变体，这将需要类似的迭代步骤。

I suppose there's also a purely mathematical method to come up with this, but I image it would involve a variation of the LCM algorithm, which would require similar iterative steps.

这篇关于如何检查两个日期系列是否重叠并确定它出现的第一个日期？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！