擅长:python、mysql、java
<p>让我们先把自己限制在最简单的情况下:找到一个合适的数据结构,它允许快速实现<strong>FirstFreeSlot()</strong>。在</p>
<p>自由时隙存在于二维空间中:一个维度是开始时间s,另一个维度是长度d。<strong>FirstFreeSlot(d)</strong>有效地回答了以下查询:</p>
<p>最小s:d>;=d</p>
<p>如果我们把s和d看作笛卡尔空间(d=x,s=y),这意味着要找到一条垂直线包围的子平面上的最低点。一个<a href="http://en.wikipedia.org/wiki/Quadtree" rel="nofollow">quad-tree</a>,可能在每个节点中有一些辅助信息(即,所有叶的最小值),将有助于有效地回答这个查询。在</p>
<p>对于<strong>Enqueue()</strong>在资源限制的情况下,考虑为每个资源维护一个单独的四叉树。四叉树还可以回答以下查询</p>
<p>最小s:s>;=s&d>;=d</p>
<p>(限制起始数据所必需的)以类似的方式:现在一个矩形(在左上角打开)被切掉,我们在该矩形中寻找min s。在</p>
<p><strong>Put()</strong>和<strong>Delete()</strong>是四叉树的简单更新操作。在</p>
<p><strong>重新计算()</strong>可以通过<strong>Delete()</strong>+<strong>Put()</strong>实现。为了节省不必要操作的时间,定义触发重新计算的足够(或者,理想情况下,足够+必要)条件。<a href="http://en.wikipedia.org/wiki/Observer_pattern" rel="nofollow">Observer</a>模式在这里可能有帮助,但请记住,将重新调度的任务放入FIFO队列或按开始时间排序的优先级队列中。(您希望在接管下一个任务之前完成对当前任务的重新安排。)</p>
<p>更一般地说,我相信您已经意识到大多数类型的调度问题,特别是那些有资源限制的问题,至少是NP完全的。所以在一般情况下,不要期望一个运行时良好的算法。在</p>