Idle Time for Heap Sort

Question

Ciao c'è questa domanda in un libro di testo di Algorithm che mi sono perso e non capisco nemmeno la domanda. Ecco la domanda:

Tempo di inattività. Supponiamo che una macchina parallela elabori N lavori. Scrivi un programma che, dato l'elenco degli orari di inizio e fine lavoro, trova l'intervallo più lungo in cui la macchina è inattiva e l'intervallo più lungo in cui la macchina non è inattiva.

Qualcuno sarebbe in grado di spiegare la domanda prima e magari darmi pseudo codice che sarebbe super utile?

Answer 1

Si dispone di una macchina in grado di eseguire più lavori contemporaneamente. Quando la macchina non sta elaborando alcun lavoro, è inattiva. Viene fornito un elenco di orari di inizio e fine di tutti i lavori e viene chiesto quando la macchina è inattiva, quindi quando non è in esecuzione alcun lavoro.

Quindi, dato questo calendario:

• Giobbe 1: inizia alle 00:00 e termina alle 10:00
• Giobbe 2: inizia alle 11:00 e termina alle 12:00
• lavoro 3: Inizia alle 05:00 e termina alle 06:00

La macchina era inattiva tra le 10:00 e le 11:00, questo è l'intervallo solo e più grande.

Se i posti di lavoro si ripetono ogni giorno c'è un altro intervallo da 12:00 a 00:00, ma per mantenere la semplice esempio si può assumere questi lavori eseguiti solo una volta.

Pseudo codice:

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

questione non specifica se inizio e di fine indicati in coppie o separatamente. C'è un semplice algoritmo per casi meno semplici, quando vengono dati separatamente, qui. Quindi abbiamo tutte le volte in un unico elenco ma conserviamo le informazioni se inizia l'ora del lavoro o termina il lavoro.

ad esempio:

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

quindi ordinare l'elenco per ora:

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

di cui abbiamo bisogno di un contatore di posti di lavoro aperti e siamo in grado di elaborare l'elenco, incremento del contatore quando il tempo di avvio viene elaborata e contatore di decremento al termine del tempo di fine lavorazione; Se il contatore è 0 significa che entriamo in stato di inattività.

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