От­сор­ти­ру­ем дан­ные в таб­ли­це так, чтобы все не­за­ви­си­мые про­цес­сы ока­за­лись в на­ча­ле таб­ли­цы и любой про­цесс был рас­по­ло­жен после всех про­цес­сов, от ко­то­рых он за­ви­сит. Также в таб­ли­цу до­ба­вим стол­бец «Время окон­ча­ния про­цес­са» и за­пи­шем туда дли­тель­но­сти не­за­ви­си­мых про­цес­сов.

Далее рас­счи­та­ем время вы­пол­не­ния остав­ших­ся про­цес­сов:

f(4)  =  7 + f(3)  =  7 + 9  =  16;

f(5)  =  6 + f(3)  =  6 + 9  =  15;

f(6)  =  2 + f(5)  =  2 + 15  =  17;

f(8)  =  2 + f(7)  =  2 + 22  =  24;

f(11)  =  6 + f(9)  =  6 + 7  =  13;

f(12)  =  6 + f(10)  =  6 + 8  =  14;

f(3)  =  5 + max(f(1), f(2))  =  5 + 4  =  9;

f(7)  =  5 + max(f(4), f(6))  =  5 + 17  =  22.

По­стро­им диа­грам­му вы­пол­не­ния каж­до­го про­цес­са и рас­смот­рим когда могут вы­пол­нять­ся од­но­вре­мен­но 4 про­цес­са.

За­ме­тим, что пер­вые че­ты­ре про­цес­са можно на­чи­нать в любой про­ме­жу­ток вре­ме­ни, так как они не­за­ви­си­мы. Тогда, если сдви­нуть время на­ча­ла про­цес­сов 9 и 10 (новое время обо­зна­че­но крас­ным), можно по­лу­чить мак­си­маль­ную про­дол­жи­тель­ность от­рез­ка вре­ме­ни (в мс), в те­че­ние ко­то­ро­го воз­мож­но од­но­вре­мен­ное вы­пол­не­ние четырёх про­цес­сов:

Мак­си­маль­ная про­дол­жи­тель­ность от­рез­ка вре­ме­ни (в мс), в те­че­ние ко­то­ро­го воз­мож­но од­но­вре­мен­ное вы­пол­не­ние четырёх про­цес­сов равна 7.

Ответ: 7.