Задание 22 ЕГЭ: многопроцессорная система / таблица процессов — как разобраться?
Дана таблица: процесс, его длительность, и от каких процессов он зависит (B зависит от A — значит начнётся только после завершения A). Просят найти минимальное общее время выполнения или когда завершится конкретный процесс. С чего начать и как это считать?
3 ответа
Это задача про критический путь по таблице зависимостей. Время завершения процесса = (максимальное время завершения всех процессов, от которых он зависит) + его собственная длительность. У процессов без зависимостей время старта = 0.
Идёшь по таблице, для каждого процесса берёшь максимум времён окончания его «родителей» и прибавляешь длительность. Если зависимостей нет — просто его длительность. Минимальное общее время = максимум по всем временам завершения. Часто это можно посчитать прямо руками на черновике в 2 прохода, кодить не обязательно.
finish[i] = max(finish[родителей]) + длит[i]. Ответ — максимум по всем finish. Можно и руками.
Через критический путь.
