Демоверсия 2023
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения
процесса A. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения
в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Типовой пример организации данных в файле:
|
ID процесса B |
Время выполнения процесса B (мс) |
ID процесса(-ов) A |
|
1 |
4 |
0 |
|
2 |
3 |
0 |
|
3 |
1 |
1; 2 |
|
4 |
7 |
3 |
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Решение данной задачи сводится к расчету того, через сколько закончится каждый из процессов. Независимые могут начаться сразу, и закончатся в момент времени, соответствующий длительности их выполнения. Процессы которые зависят от других, смогут начаться, как только закончится самый долгий из тех, от которых они зависят, и соответственно время, когда они закончатся, можно рассчитать как сумму момента окончания самого долгого, от которого они зависят и их длительности.
Максимальное значение - это f(8). Т.е. самый долгий процесс длится 17 миллисекунд, значит минимальное время через которое сможет закончиться вся совокупность процессов - 17 миллисекунд.
Ответ: 17.