logo标签列表

优先处理重叠日期范围。

algorithmdateoverlapping
4

我在其他地方找到了类似的问题，但没有考虑过优先级。

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

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

假设我有三个日期范围的来源，名称分别为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    |

我猜你能看出这要往哪个方向发展……需要做很多交叉检查等操作，但在纸上看起来似乎可行。如果有人需要的话，我可以更好地解释一下算法，但我认为它不难跟踪。如果有更高优先级的有序列表，则不会写入任何内容。当删除较高优先级时，下一个最大值重新打开。
也许有更好、更具体的想法吗？谢谢你的时间！
4个回答
1
另一种方法是相反的构建方式，从最低优先级开始填充表格，随着填充更高优先级的项目，简单地覆盖日期。这样就避免了创建顺序列表并跟踪哪些项目已打开等待启动的情况。
注意：我应该提前说一下，以下算法几乎肯定不太有效率（我没有做过数学计算，但直觉告诉我它不太有效率）。这只是另一种解决问题的方法。
通过分组每个事件的开放和关闭日期，可以更有利。出于简单起见，我将开始日期到结束日期称为“事件”。因此，您首先要添加每个最低优先级的事件。然后，按优先级和日期组织数据进行查看，如下所示：
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之间。如果我们抽象地思考一下，会得到三种不同的情况：
  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  |

从这里推断出其余的流程应该不难。（如果您需要更多解释，请让我知道。）

根据信息组织方式和涉及的数据结构，这种方法可能不如您所描述的那样高效。但我认为这种方法更加直观，因为您首先安排最低优先级，然后修改它们以腾出时间为更高优先级。我并没有看到您提供的解决方案有问题，并且它确保您只查看每个条目一次（而我的方案可能会多次查看项目，或修改最终被后续事件覆盖的项目）。

我不建议您使用我的解决方案，但您没有要求效率，只是想换一种看待问题的方式。

嘿，唐，谢谢你的回答。是的，我只是询问替代方案，因为有时候你会完全陷入自己的解决方案中，无法考虑其他方式，所以我想知道是否有不同或已知的方法来解决这个问题。我会想一想。干杯 :) - Dimitrios K.
我还没有遇到过类似的问题，但是为了帮助你找到正确的方向，你所定义的问题通常被称为“调度”问题。因此，搜索这个词可能会对你有所帮助（你在问题中没有使用这个术语，所以我假设你不知道它）。我发现的大部分内容都没有规则集，可以改变事件的长度，这给你带来了一个非常独特的问题。 - Don
0

Bartel算法使用优先队列非常好 - 该算法在不连续的区间上会中断，因为：

    while( A[i].Open > H[0].Close )
{
    if( H[0].Close >= from ):
        We have a new result; R( S = H[0]; Open = from; Closed = H[0].Closed )
        Set from = H[0].Closed + 1;
    Dequeue H[0]
}

对于不重叠区间的情况，实际上应该是：

while( A[i].Open > H[0].Close )
{
    if( H[0].Close >= from ):
        We have a new result; R( S = H[0]; Open = from; Closed = H[0].Closed )
        Set from = A[i].from;
    Dequeue H[0]
}

这是来自下一个时间间隔的最新消息

考虑以下区间([interval], prio): ([1,4],0), ([2,3],1), ([5,6],0)。期望的结果是：{ [1,2], [2,3], [3,4], [5,6] }；我认为你的建议在结果中的[3,4]会出错。我认为你需要在外部循环（设置i = i + 1的循环）中添加一些内容，以便在Enqueue(A[i])之后，设置from = MAX(from, H[0].Open)；或者如果(H[0]==A[i])，则from = A[i].Open。我应该检查我的原始代码以确保。 - Bartel
0

我最近写了一个这样的算法。我保留了两个数组：一个是像你的一样的结果数组，另一个是区间S的数组（不是日期，而是你所称的ID）。最初，数组S按照开放的'('进行排序，而结果为空。

我还保持了一种排序列表，但与你的不同之处在于它不是按优先级排序，而是按关闭')'排序。这使得从订单列表中快速删除不再需要考虑的区间变得容易，因为您可以保留索引，而该索引之前的所有内容都已过去。

然而，实际实现没有单独的订单列表，而是重新使用了S：

对于i>index_1的S[i]，输入按开放的'('排序

对于i<index_1的S[i]，订单列表按关闭的')'排序

对于i<index_2的S[i]，“已过去”

因此，当创建结果条目并且我们需要获取下一个S时，只需要搜索范围index_1->index_2（具有最高优先级的区间）。

让我们看看我是否可以重新创建前几次迭代：

// initialize
S = [S1a,S2a,S3a,S2b,S1b,S3b,S1c]
R = []
index_1 = 0;
index_2 = 0;

// first result starts at smallest open
R1.start = S1a.open()
date = S1a.open() // 'current time'

// check if next entry in S ends the result R1
S[++index_1] = S2a: S2a.open() < S1a.close and S2a.Priority < S1a.Priority

// this does not end R1 -> keep S sorted, update index_2
S[index_1 - 1] = S1a, S[index_1] = S2a, S1a.close < S2a.close // -> OK! no swap needed
date = S2a.open()
S[index_2] = S1a: S1a.close() < date // -> OK! no update of index_2 needed

// check if next entry in S ends the result R1
S[++index_1] = S3a: S3.open() > S1a.close

// this ends R1 -> create it, update index_2
date = S1.close()
R1.close() = date
S[index_2] = S1a: S1a.close() = date // -> S1a is 'past'
index_2++ // update index_2
S[index_2] = S2a: S2a.close() < date // -> OK! no further update of index_2 needed

// find the next interval for R2
search S[i] index_2 <= i < index_1 and pick max priority
in this case index_2 = 1 and index_1 = 2 so we only need to check one entry (S2a)

R2.open = max( date, S2a.open() )

// continue...

抱歉如果有任何小错误，但我希望传达了算法的思想（并不是要提供所有细节）

关于性能，我不确定，这取决于数据类型，我猜测（如果许多间隔之间存在重叠，则索引_2 - 索引_1的范围很大，并且每次将新间隔添加到顺序列表时，在该范围内进行搜索以及按close ')'排序变得昂贵；但是，如果您只有相邻间隔之间的重叠，index_2 - index_1将仅为1个元素，因此上述两个操作都非常便宜）

如果这是一个问题，那么它肯定更少占用内存。

0
上个星期我写了另一个算法，其最坏情况复杂度得到了改善。它具有一个优先级队列（我使用了堆）和一个按开放日期排序的间隔数组，起初是空的。
A = [S1a,S2a,S3a,S2b,S1b,S3b,S1c]
H = []

我们对A进行迭代（时间推进）；将A的每个元素入队到队列中。由于它是一个优先级队列，根元素H[0]包含具有最高优先级的元素。一旦它关闭，根元素将被出队。

您会发现结果是优先级队列的根元素，其间隔与该元素成为根（最高优先级）的“时间”相对应，直到它从队列中出队（关闭）或被新入队的元素“压下”（在关闭之前被更高优先级的间隔取代）。

更正式地说：

当我们取A[i++]中的下一个元素（时间推进）时，我们将其与优先级队列中当前最高元素H[0]进行比较，并检查A[i].Open > H[0].Close。

while( A[i].Open > H[0].Close )
{
    if( H[0].Close >= from ):
        We have a new result; R( S = H[0]; Open = from; Closed = H[0].Closed )
        Set from = H[0].Closed + 1;
    Dequeue H[0]
}

一旦 A[i].Open < H[0].Close，我们将 A[i] 入队到优先队列中。有两种可能发生;

要么 A[i] 是具有最高优先级的区间，成为新的根。然后我们得到了一个新结果; R（S = 旧根 H[0]; 开始 = 来自; 结束 = A[i].Open）；设置开始 = A[i].Open

要么 A[i] "消失" 在堆中，H[0] 不改变；然后继续。

一旦我们遍历完 A；我们继续出队，如果需要创建结果；直到队列为空。

对于内存，您可以使用单个数组来实现这个功能，并且只对该数组进行交换；前 x 个索引是堆；最后 y 个元素是数组 A。

在您的示例上运行：

// i = 0：入队 S1a

A = [S2a,S3a,S2b,S1b,S3b,S1c]
H = [S1a]

// i = 1：将S2a入队

A = [S3a,S2b,S1b,S3b,S1c]
H = [S1a,S2a]

// i = 2：第一个结果（----|; 从S1a中出队列；将其加入S3a队列

A = [S2b,S1b,S3b,S1c]
H = [S2a,S3a]

// i = 3: 第二个结果 |xx|; 出队列 S2a（这使得 S3a 成为根节点）；入队列 S2b；第三个结果 |oo|（因为 S2b 从根节点位置驱动 S3a）

A = [S1b,S3b,S1c]
H = [S2b,S3a]

// i = 4; 入队 S1b; 第四个结果 |xx|

A = [S3b,S1c]
H = [S1b,S3a,S2b]

// i = 5; 将 S3b 入队

A = [S1c]
H = [S1b,S3a,S2b,S3b]

// i = 6; 第五个结果 |----); 不创建结果的情况下出队列S1b、S3a、S2b和S3b; 将S1c入队列

A = []
H = [S1c]

// 第六个结果 (--); 出队列 S1c; 停止

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接