堆排序的空闲时间

Question

嗨,在算法的教科书中有这个问题,我迷失了,甚至不理解这个问题.这是一个问题:

空闲时间.假设并行机器处理N个作业.编写一个程序,根据作业开始和结束时间列表,找到机器空闲的最大间隔和机器不空闲的最大间隔.

有人能够先解释这个问题,也许会给我一些超级有用的伪代码吗？

Answer 1

您拥有一台可以同时执行多个作业的机器。当机器根本不处理任何作业时，它处于空闲状态。您将获得所有作业的开始和停止时间的列表，并询问机器何时空闲以及何时没有作业运行。

因此给出这个时间表：

• 作业 1：00:00 开始，10:00 结束
• 工作2：11:00开始，12:00结束
• 作业 3：05:00 开始，06:00 结束

10:00至11:00之间机器处于空闲状态，这是唯一且最大的间隔。

如果作业每天重复，则从 12:00 到 00:00 会有另一个时间间隔，但为了使示例简单，您可以假设这些作业仅运行一次。

伪代码：

busy = []
for each Job
    find intervals in busy that overlap with job
    if no overlapping intervals are found
        add job interval to busy
    else
       remove overlapping intervals from busy  
       merge overlapping intervals with job interval
       add new interval to busy


find longest busy interval
create non-busy intervals from busy intervals
find longest non-busy interval