0

我有一个日期范围列表。

05/01/2012 - 07/01/2012
07/02/2012 - 09/05/2012
01/01/2012 - 03/31/2012
08/01/2012 - 12/31/2012

现在的问题是验证给定列表是否涵盖特定范围内的所有日期。例如，此列表涵盖 05/01/2012 - 12/31/2012 范围内的所有日期，但非 01/01/2012-12/31/2012，因为此列表未涵盖 4 月日期。假设是，

  1. 日期范围有效 - 开始日期 <= 结束日期。
  2. 日期范围可能会重叠，如上述第 2 和第 4 的情况。
  3. 列表不以任何方式排序。

到目前为止，我所做的是测试异常值，例如，

查找最小开始日期和最大结束日期 - 如果测试日期范围的开始日期和/或结束日期分别小于/大于这些日期，则测试失败。

但是，在中间检查任何错过的日期的最佳策略是什么？提前致谢！

4

5 回答 5

3

最简单的策略是解析所有涉及的日期。O(N)

按开始日期对日期进行排序。 O(N log N)时间

将结束日期与下一个开始日期进行比较（忽略任何倒退的结束日期）O(N)

如果到下一个开始日期的一端超过一天，则您有一个差距。

于 2013-01-07T20:42:04.543 回答
2

首先要做的是修复您的输入数据。

  1. 按开始日期排序所有范围
  2. 通过设置开始日期删除所有重叠
  3. 消除任何因 2 而消失的范围

所以你的范围会变成

01/01/2012 - 03/31/2012
05/01/2012 - 07/01/2012
07/02/2012 - 09/05/2012
09/06/2012 - 12/31/2012

然后你只需要找到丢失的日期，看看你是否能弄清楚如何做到这一点。

于 2013-01-07T20:44:02.167 回答
0

将日期转换为自 1970 年 1 月 1 日（或其他参考日期）以来的天数。

那么你的问题就变成了找到丢失的整数。

于 2013-01-07T20:42:54.557 回答
0

生成范围内的每个日期，将它们放入列表中并测试以查看您的候选人是否在该列表中。

于 2013-01-07T20:42:58.240 回答
0

尝试以下操作（按最小日期对列表范围进行排序后）：-

  i=0
  a=min_date at 0 position
b=max_date corresponding to a

while list has elements
   c= min_date at (i+1) position
   d=max_date corresponding to c

if (b< (c - 1 day))
then there is a gap;
else 
{ 
if(b<d)   // done to handle the situation :- 06/07/2012 - 12/31/2012
          // 08/07/2012 - 11/31/2012. Then b will still remain 12/31/2012 after if condition
{
  b=d;
}
}
i=i+2;
end while;

以上只会在列表中找到任何缺失的日期。

于 2013-01-07T20:51:30.737 回答