Idle Time for Heap Sort

Question

Hi there is this question in an Algorithm's textbook which I am lost and don't even understand the question. Here is the question:

Idle time. Suppose that a parallel machine processes N jobs. Write a program that, given the list of job start and finish times, finds the largest interval where the machine is idle and the largest interval where the machine is not idle.

Would someone be able to explain the question first and maybe give me pseudo code which would be super useful?

Answer 1

You have a machine that can execute multiple jobs at the same times. When the machine is not processing any jobs at all, it is idle. You are given a list of start and stop times of all the jobs and asked when the machine was idle, so when no jobs were running.

So given this schedule:

• Job 1: Starts at 00:00 and ends at 10:00
• Job 2: Starts at 11:00 and ends at 12:00
• Job 3: Starts at 05:00 and ends at 06:00

The machine was idle between 10:00 and 11:00, this is the only and largest interval.

If the jobs repeat every day there is another interval from 12:00 to 00:00, but to keep the example simple you can assume these jobs only run once.

Pseudo code:

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

Answer 2

Question does not specifies if start and finish times given in pairs or separately. There is a simple algorithm for less simple case, when they are given separately, here. So we have all times in a single list but keep information if it start job time or finish job time.

for example:

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

then sort this list by time:

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

Than we need a counter of open jobs and we can process list, increment counter when start time is processed and decrement counter when finish time is processed; If counter is 0 it means that we enter idle state.

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;
          }
     }
}