4

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

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    |

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

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

谢谢你的时间！

4

4 回答 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 Openand之间的日期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  |

不难推断其余部分是如何到位的。（尽管如果您需要更多解释，请告诉我。）

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

我不推荐我的解决方案而不是你的解决方案，但你没有要求效率，只是一种不同的看待它的方式。

于 2013-10-02T20:35:54.530 回答
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]; Open = from; Closed = 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: 第一个结果 (----|; dequeue S1a; enqueue 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; 停止

于 2014-08-17T12:33:48.230 回答
0

我最近写了一个算法来做到这一点。我保留了两个数组：一个像你的结果和一个间隔 S 数组（不是日期，而是你所谓的 ID）。最初，数组 S 在 open '(' 上排序，结果为空。

我还保留了一种订单列表，但与您的不同之处在于它不是按优先级排序，而是按关闭“）”排序。这样可以快速从订单列表中删除由于“过去”而不再需要考虑的间隔：您可以在该索引过去之前将索引保留为所有内容。

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

S[i] for i > index_1 是在 open '(' 上排序的输入

S[i] for i < index_1 是关闭时排序的订单列表 ')'

S[i] for i < index_2 '谎言过去'

所以当一个结果条目被创建并且我们需要获取下一个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...

抱歉有任何小错误，但我希望能传达算法的想法（我无意提供所有细节）

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

如果这是一个问题，它肯定会更便宜的内存。

于 2013-10-15T21:32:12.367 回答
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]
}

那是新的来自下一个间隔

于 2014-12-25T10:21:47.327 回答