Задание №22 — Многопоточность

Решение:

Момент завершения процесса $B$ равен $F(B) = \max F(A_i) + t(B)$, где $A_i$ — процессы, от которых он зависит; независимый процесс завершается в момент $t(B)$. Время работы всей совокупности — наибольшее из значений $F$. При увеличении $t$ это время не убывает, поэтому нужно взять наибольшее целое $t$, при котором оно ещё не превышает 19 мс.

Подставим $t = 9$ и заполним столбец $F$:

ID процесса	Время выполнения, мс	Зависит от	Момент завершения, мс
1	4	0	4
2	3	0	3
3	2	1; 2	6
4	3	3	9
5	$t$	0	9
6	5	4; 5	14
7	5	0	5
8	6	7	11
9	5	6; 8	19
10	12	0	12
11	2	10	14
12	2	11	16

Наибольшее значение равно 19 мс, условие «не более 19 мс» выполнено. При $t = 10$ общее время стало бы равно 20 мс, что больше 19, поэтому 9 — максимально возможное целое значение.

Тот же перебор программой:

# данные из прилагаемого файла; None — неизвестное время t
data = {
     1: (4, []),
     2: (3, []),
     3: (2, [1, 2]),
     4: (3, [3]),
     5: (None, []),
     6: (5, [4, 5]),
     7: (5, []),
     8: (6, [7]),
     9: (5, [6, 8]),
    10: (12, []),
    11: (2, [10]),
    12: (2, [11]),
}

def total(t):
    finish = {}
    for i in sorted(data):
        dur, deps = data[i]
        if dur is None:
            dur = t
        finish[i] = max([finish[d] for d in deps], default=0) + dur
    return max(finish.values())

print(max(t for t in range(1, 1000) if total(t) <= 19))

Ответ: 9