0

给定具有打开或关闭的单个状态的任何一系列输入日期，这样至少有一个输入日期（打开状态）导致添加单个日期（关闭，最大日期）以完成输出序列您将使用什么算法来生成符合以下条件的输出？

1. 没有连续的开放日期和连续的关闭日期。

2. 对于每个开放日期，只有一个关闭日期。

3. 第一个日期应该是 Open，最后一个日期应该是 Closed。

4. 除了第一个开盘日期和最后一个开盘日期外，每个开盘日期应该紧跟上一个开盘日期，或者换句话说，每个关盘日期应该是下一个开盘日期的前一天。

5. 最终日期为 Closed 和 Max date（本例中为 9999-12-31）

这不是一个家庭作业，我已经在 C# 中实现了它，它的生产代码将执行数百万次。性能很重要，是的，但在可读性方面非常次要。我使用的算法效果很好，但看起来很糟糕。欢迎任何语言。我会根据需要翻译。谢谢。

示例 1

input:
[2000-01-01,open] 

output: 
[2000-01-01,open]
[9999-12-31,closed]

示例 2

input: 
[2000-01-01,open]
[2001-01-01,open]

output: 
[2000-01-01,open]
[2000-12-31,closed]
[2001-01-01,open]
[9999-12-31,closed]

示例 3

input: 
[2000-01-01,open]
[2004-04-30,closed]

output: 
[2000-01-01,open]
[2004-04-30,closed]
[2004-05-01,open]
[9999-12-31,closed]

示例 4

input: 
[2000-01-01,open]
[2000-03-17,open]
[2002-09-11,closed]
[2003-04-07,closed]

output: 
[2000-01-01,open]
[2000-03-16,closed]
[2000-03-17,open]
[2002-09-11,closed]
[2002-09-12,open]
[2003-04-07,closed]
[2003-04-08,open]
[9999-12-31,closed]

我敢问哪一类语言最能解决这类问题？

4

3 回答 3

5
  1. 按日期对输入进行排序。
  2. 遍历输入，跟踪当前状态。
  3. 如果状态为打开并且遇到打开日期，则插入关闭日期。
  4. 如果状态为关闭并且遇到关闭日期，则插入打开日期。
  5. 如果状态已关闭并且遇到的打开日期不是上一个关闭日期的第二天，则插入一个打开日期和一个关闭日期以填补该空白。
  6. 完成对输入的迭代后，如果状态为打开，则插入最终关闭日期。
  7. 完成输入迭代后，如果状态已关闭且最终关闭日期不是 9999-12-31。插入最后的开放和关闭日期。
于 2012-08-29T13:34:57.863 回答
0

您可以首先生成所有开放日期的列表，然后通过从除第一个开放日期之外的每个日期减去一天来计算结束日期：

C# 伪代码：

  var opendates = input.Select ( date =>
      date.Type == closing ? date.Date + 1day : date.Date
  ).Sort ();
  closingdates = opendates.Skip (1).Select (date => date - 1).Append ( new Date [] { 9999-12-31 } );
于 2012-08-29T13:32:52.043 回答
0

所以解决方案应该很快，因为性能在这里至关重要。它还应该支持在线处理，因此当系统运行时，您可以随时添加新的开/关日期并立即获得更新的时间表。

由于这个问题的主要操作是排序，我建议使用堆。堆中的每个节点都存储一个日期/状态对。该算法以空堆启动，并不断将其开发为读取输入。当有新数据到来时，算法将其插入到树中，这需要 O(lgN)。当有请求拉动计划时，算法会执行有序遍历，这需要 O(N)。该算法还应该偶尔平衡一次以获得更好的性能。

于 2012-08-29T16:27:56.803 回答