堆排序的空闲时间

Question

您好，这是一道与算法相关的问题，需要翻译如下内容：

空闲时间。假设一个并行机器处理N个作业。编写一个程序，给定作业开始和完成时间的列表，找到机器空闲的最长时间间隔和机器非空闲的最长时间间隔。

请问是否需要先解释一下问题，并提供伪代码？

- Navleen Singh

---

我正在从这个问题中删除排序和堆排序标签，因为该问题并不直接涉及它们。 - templatetypedef

Answer 1

问题没有指定起始时间和结束时间是成对给出还是分别给出。如果分别给出，那么有一个简单的算法可以解决不太简单的情况，详情请看这里。 因此，我们将所有时间放在一个列表中，但保留开始工作时间或完成工作时间的信息。

例如：

13:00 start    
15:00 finish
8:30  start
10:00 finish
9:00  start    
12:00 finish

然后按时间对这个列表进行排序：

8:30  start
9:00  start
10:00 finish
12:00 finish
13:00 start
15:00 finish

我们需要一个开放职位的计数器，然后可以处理列表，在开始时间被处理时增加计数器，在结束时间被处理时减少计数器；如果计数器为0，则表示我们进入空闲状态。

list.sort()
open_jobs = 0
state_changed_time = list[0].time; 
max_idle_interval = -1;
max_not_idle_interval = -1;
for each (element in list)
{
     if (element.type == start)
     {
          if(open_jobs == 0)
          {
               interval = element.time - state_changed_time;
               if (interval > max_idle_interval) max_idle_interval = interval;
               state_changed_time = element.time;
          }
          open_jobs +=1;
     }
     if (element.type == finish) 
     {
          open_jobs -= 1;
          if(open_jobs == 0)
          {
               interval = element.time - state_changed_time;
               if (interval > max_not_idle_interval) max_not_idle_interval = interval;
               state_changed_time = element.time;
          }
     }
}

- Lurr

Answer 2

你有一台机器，可以同时执行多个作业。当机器完全不处理任何作业时，它处于空闲状态。你得到了所有作业的开始和结束时间列表，并被问及机器何时处于空闲状态，即没有作业在运行时。

给定这个日程安排：

作业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

- M.P. Korstanje

---

在12:00到5:00之间，机器空闲的最长时间间隔是多少？ - Navleen Singh

在12:00和00:00之间。如果你假设一个循环的一天，在这种情况下并不是不合理的，但会使算法变得更加复杂，这可能不是你想要开始的内容。 - M.P. Korstanje

正如@NavleenSingh所指出的那样，你的数据或答案可能是错误的。此外，任何示例数据都应包括重叠部分，因为这是问题的隐含部分。此外，你的伪代码最多令人困惑，而在更糟糕的情况下可能无法实现或只是逻辑上不正确。由于你已经将重要部分作为抽象概念掉了，所以很难判断。 - RBarryYoung

好的，我明白了，你们一天有12个小时。虽然有点令人困惑，但一旦你知道了这一点，它还是有意义的。不过伪代码仍然是一个问题。 - RBarryYoung

我理解了，但如果我还是困惑的话，我会问的，谢谢！ - Navleen Singh

@RBarryYoung 这就是伪代码的意义所在。实际代码或数学证明会太过复杂。不过你可以写一个例子。 - M.P. Korstanje