Как решать задание 22 ЕГЭ по информатике (процессы, многопоточность)?

Задание 22 — анализ зависимостей процессов. Дана таблица: ID процесса, его длительность T, и список процессов-предшественников B (которые должны завершиться раньше). Нужно найти минимальное общее время выполнения всех процессов (они идут параллельно, где можно).

Идея: время окончания процесса = его длительность + максимальное время окончания среди всех его предшественников. У процессов без предшественников старт в 0.

finish[p] = T[p] + max(finish[b] for b in предшественники p) (или просто T[p], если их нет).

Ответ — максимум по всем finish (момент, когда закончится самый поздний процесс).

На Python (обрабатывая в порядке зависимостей):

finish = {}
# при условии, что процессы заданы так, что предшественники идут раньше
for p in processes:           # p: (id, T, [предшественники])
    pid, t, preds = p
    start = max((finish[b] for b in preds), default=0)
    finish[pid] = start + t
print(max(finish.values()))

Частые ошибки:

• складывать длительности всех процессов (это была бы последовательная работа — неверно, они параллельны);
• брать сумму времён предшественников вместо максимума;
• неверно прочитать столбец «программа B, требуемая для запуска» (это и есть предшественник).

Это, по сути, поиск самого длинного пути по графу зависимостей.