每个任务都有一个最早开始时间。我们将所有tasks按照最早开工时间依次处理并放入任务池中。任务池中的tasks意味着你可以选择开工减少它们的工作量,当然也可以不开工。如果不在池中的tasks则无法做任何操作。
对于任务池中的tasks,我们将其按照最晚开工时间保持有序。最晚开工时间的意思是,你必须在这个时刻开工并且直到全部完成其工作量,否则就来不及了。
我们令runtime表示当前(已经将部分tasks放入任务池)我们已经(不得不)开工的时长。我们现在需要考虑一个新任务A,准备加入任务池。而此刻任务池中某任务B对应着最早的“最晚开工时间”。此时,如果B的最晚开工时间晚于A的最早开工时间,那么意味着当前没有任何due time,我们不着急开工,可以再拖一拖,可以将A先放入任务池再说。而如果B的最晚开工时间早于A的最早开工时间,意味着B等不及了,我们在将A放入任务池之前必须开工了,那么至少开工多长时间呢?三种情况:
- 如果当前的runtime已经比B需要的工作时长多。那么说明任务B已经完成了,那么将B从任务池中拿走。
- 如果在A的最早开工时间之前就可以把B做完,那么需要再跑:B需要的工作时长减去已经开工的runtime。
- 如果在A的最早开工时间之前并不能把B做完,那么需要再跑:A的最早开工时间减去B的最晚开工时间,也就是将时间线拉到A的最早开工时间。
然后我们需要将A放入任务池。但是任务池里面的tasks都已经跑过runtime了,A与它们并没有直接的可比性呀。我们做一个处理:假设A的最晚开工时间为t,需要工作时长为d,那么A就等效于任务A',其最晚开工时间为t-runtime,需要工作时长为d+runtime。这样将A'放入任务池后,任务池中的所有任务都可以认为已经跑过了runtime的时间,彼此之间可以放心地按照“最晚开工时间”排序。