algorithm - 优先处理重叠的日期范围

Question

我发现了类似的问题，但没有考虑优先级。

R : (------------|xxxxxxx|ooo|xx|----------------)   (---)

S1: (------------)              (----------------)   (---)
S2:      (xxxxxxxxxxxxxxx)   (xxxxxx)
S3:                   (ooooooo)           (oo)

假设我有 3 个日期范围来源，名称为 S1、S2 和 S3，优先级分别为 1,2 和 3(1 为最高)和结果 R。我需要结果是不重叠的日期范围最高优先级优先。

我想到了一个解决方案，但它很顺序。首先，我创建了一个按日期升序、优先级降序排列的表(如果发生日期冲突，最高优先级在表中排在第一位)及其 ID 和操作(开放或关闭范围):

ID  | Action | Priority | Date |
--------------------------------
S1a | Open   |    1     |  1   |
S2a | Open   |    2     |  2   |
S1a | Close  |    1     |  3   |
S3a | Open   |    3     |  4   |
S2a | Close  |    2     |  5   |
S2b | Open   |    2     |  6   |
S3a | Close  |    3     |  7   |
S1b | Open   |    1     |  8   |
S2b | Close  |    2     |  9   |
S3b | Open   |    3     |  10  |
S3b | Close  |    3     |  11  |
S1b | Close  |    1     |  12  |
S1c...

然后我开始迭代这个表并填充一个有序列表和一个结果表:

所以第一行是:

Order List:          Result:
ID | Priority |      ID | Action | Date  |  
S1a|    1     |      S1a|  Open  |  1    |

第二行，添加了 S2a 的开始日期，但没有写任何东西，因为表中存在更高的优先级:

Order List:          Result:
ID | Priority |      ID | Action | Date  |  
S1a|    1     |      S1a|  Open  |  1    |  
S2a|    2     |      

第三行，关闭 S1a，写入关闭日期，由于 S2a 移至列表顶部，它也写入 S2a 的打开日期。

  Order List:          Result:
  ID | Priority |      ID | Action | Date  |  
x S1a|    1     |      S1a|  Open  |  1    |  
  S2a|    2     |      S1a|  Close |  3    |
                       S2a|  Open  |  3    | 

我猜你能看出这是怎么回事……大量的交叉检查等，但在纸上它似乎有效。如果有人需要，我可以更好地解释算法，但我认为它并不难理解。如果有序列表中有更高的优先级，则不写入任何内容。当更高的优先级被移除时，下一个最大的将再次打开。

也许有人有更好、更具体的想法？

感谢您的宝贵时间!

Answer 1

解决这个问题的另一种方法是以相反的方式构建它，首先填充具有最低优先级的表，然后在用更高优先级的项目填充它时简单地覆盖日期。这样就不必创建订单列表并跟踪哪些项目已打开等待启动。

NOTE: I should say up front that the following algorithm is almost assuredly less efficient (I didn't do the math but intuition tells me it's less efficient). It's simply another way to approach the problem.

以这种方式将每个事件的开始和结束日期分组会更有益。为了简单起见，我将把开始日期到结束日期称为“事件”。因此，您首先添加每个优先级最低的事件。然后您开始查看按优先级排列的数据，然后按日期排列。像这样:

ID  | Action | Priority | Date |
--------------------------------
S3a | Open   |    3     |  4   |
S3a | Close  |    3     |  7   |
S3b | Open   |    3     |  10  |
S3b | Close  |    3     |  11  |
S2a | Open   |    2     |  2   |
S2a | Close  |    2     |  5   |
S2b | Open   |    2     |  6   |
S2b | Close  |    2     |  9   |
S1a | Open   |    1     |  1   |
S1a | Close  |    1     |  3   |
S1b | Open   |    1     |  8   |
S1b | Close  |    1     |  12  |
-------------------------------

所以简单地遍历最低优先级并将所有内容添加到结果中:

结果:

ID  | Action | Priority | Date |
--------------------------------
S3a | Open   |    3     |  4   |
S3a | Close  |    3     |  7   |
S3b | Open   |    3     |  10  |
S3b | Close  |    3     |  11  |

这是事情变得有趣的地方，现在您开始查看下一个最高优先级的事件。因此，我们遇到了第一个事件 S2a，我们所做的是在结果中搜索位于 S2a Open 和 S2a Close 之间的日期。如果我们抽象地思考一下，我们会得到 3 种不同的情况:

1. 我们找到了一个事件的开始。
2. 我们找到一个事件的结束。
3. 我们找到事件的开始和结束。

在第一种情况下，由于事件的开始将被推到更高优先级事件的结束。即设置包含的事件开始于当前更高优先级事件的 Close。

在第二种情况下，由于事件的结束发生在优先级较高的事件开始之后，因此它必须提前结束。所以我们将包含的事件的结束设置为当前更高优先级事件的 Open。

在最后一种情况下，整个事件都包含在优先级较高的事件中，因此将被完全取消。即删除开头和结尾。

因此，如果我们查看您的示例，我们有 S2a Open = 2 和 S2a Close = 5。该范围内包含的唯一日期是 S3a Open 。因此，我们将 S3a Open 的日期更改为 S2a Close 的值，即 5。现在我们的结果如下所示:

结果:

ID  | Action | Priority | Date |
--------------------------------
S2a | Open   |    2     |  2   |
S2a | Close  |    2     |  5   |
S3a | Open   |    3     |  5   |
S3a | Close  |    3     |  7   |
S3b | Open   |    3     |  10  |
S3b | Close  |    3     |  11  |

由此不难推断出其余部分是如何落实到位的。 (尽管如果您想要更多解释，请告诉我。)

根据信息的组织方式和涉及的数据结构，这可能不如您描述的方式有效。但我认为这个更直观一点，因为您首先安排最低优先级，然后修改它们以便为更高优先级腾出时间。我看不出您提供的解决方案有问题，它确实保证您只查看每个条目一次(而我的可以多次查看该项目，或修改最终被后来的事件破坏的项目)。

我不推荐我的解决方案胜过您的解决方案，但您并没有要求效率，只是以不同的方式看待它。