Downtime for sorting heaps

Question

Hi, this question was asked in the textbook "Algorithm", which I lost and do not even understand the question. Here is the question:

Downtime. Suppose a parallel machine processes N jobs. Write a program that, given the list of start and end periods of operation, finds the largest interval in which the machine is in standby mode and the largest interval when the machine is not working.

Can anyone first explain the question and maybe give me a pseudo code that will be very useful?

Answer 1

You have a machine that can perform several tasks at once. When the machine does not process any tasks at all, it does not work. You are given a list of start and end times of all tasks and are asked when the machine was inactive, therefore, when no tasks were performed.

So, given this schedule:

• Work 1: starts at 00:00 and ends at 10:00.
• Work 2: starts at 11:00 and ends at 12:00
• Work 3: starts at 05:00 and ends at 06:00.

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

If the tasks are repeated every day, there is another interval from 12:00 to 00:00, but for a simple example, you can assume that these tasks are performed only once.

Pseudocode:

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

The question does not indicate whether the start and end times will be set in pairs or separately. There is a simple algorithm for the less simple case when they are listed separately. Thus, we have all the time in one list, but we save information if it starts working hours or ends working hours.

eg:

 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 

We need a counter for open jobs, and we can process the list, increase the counter when the start time of the processing and the decrease counter when processing the end time; If the counter is 0, it means that we are entering a state of inaction.

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