Vai al contenuto principale

Informatica · Greedy

Risparmio dell'ordinamento SPT rispetto all'ordine di arrivo

Cinque clienti arrivano insieme a uno sportello con pratiche di durata, nell'ordine di arrivo, 8, 3, 10, 2, 6 minuti. Lo sportello serve un cliente alla volta dal tempo 0. Se i clienti vengono serviti nell'ordine di arrivo, sia S1 la somma dei loro tempi di completamento; se vengono serviti in ordine di durata crescente, sia S2 la somma dei tempi di completamento. Quanto vale $S1 - S2$?