<p>经过一段时间的思考。我认为<strong>段树</strong>可能更适合对这个时间轴队列建模。工作概念就像一个列表数据结构。在</p>
<p>我假设任务可以这样建模(伪代码)。作业中的任务顺序可以由开始时间确定。在</p>
<pre><code>class Task:
name=''
_seg_starttime=-1;
#this is the earliest time the Task can start in the segment tree,
#a lot cases this can be set to -1, which indicates its start after its predecessor,
#this is determined by its predecessor in the segment tree.
#if this is not equal -1, then means this task is specified to start at that time
#whenever the predecessor changed this info need to be taken care of
_job_starttime=0;
#this is the earliest time the Task can start in the job sequence, constrained by job definition
_duration=0;
#this is the time the Task cost to run
def get_segstarttime():
if _seg_starttime == -1 :
return PREDESSOR_NODE.get_segstarttime() + _duration
return __seg_startime + _duration
def get_jobstarttime():
return PREVIOUS_JOB.get_endtime()
def get_starttime():
return max( get_segstarttime(), get_jobstarttime() )
</code></pre>
<ul>
<li><strong>排队</strong>这仅仅是将一个任务节点追加到段树中,请注意将_seg_startime设置为-1,以指示它将在其前一个任务节点之后立即启动</li>
<li><strong>放入</strong>在树中插入一个段,该段由开始时间和持续时间表示。在</li>
<li><strong>删除</strong>删除树中的段,必要时更新其后续节点(假设删除的节点确实存在一个_seg_start_time)</li>
<li><strong>重新计算</strong>再次调用get_starttime()将直接获得其最早的开始时间。在</li>
</ul>
<p>示例(不考虑工作限制)</p>
^{pr2}$
<p>如果我们做一个看跌期权:</p>
<pre><code> t1.1( _segst = 10, du = 10 )
\
t2.2( _segst = -1, du = 10 ) meaning the st=20+10=30
/ \
t2.3(_segst = 20, du = 10) t1.3 (_segst = -1, du = 10 ) meaning the st = 30+10 = 30
</code></pre>
<p>如果我们删除t1.1到原始场景</p>
<pre><code> t2.2( _segst = 20, du = 10 )
\
t1.3 (_segst = -1, du = 10 ) meaning the st = 20+10 = 30
</code></pre>
<p>每个资源可以用这个间隔树的一个实例来表示
鸡蛋。在</p>
<p>从段树(时间轴)的角度来看:</p>
<pre><code>t1.1 t3.1
\ / \
t2.2 t2.1 t1.2
</code></pre>
<p>从工作角度来看:</p>
<pre><code>t1.1 <- t1.2
t2.1 <- t2.2
t3.1
</code></pre>
<p>t2.1和t2.2是用链表连接起来的,如前所述:t2.2从段树中获取它的_sg_start_时间,从链表中获取它的_job_start_时间,比较这两个时间,就可以得出它可以运行的实际最早时间。在</p>