В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы — время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Определите максимальное количество миллисекунд, когда одновременно может выполниться максимальное количество процессов.
Выполните задания, используя данные из файла ниже:
В таблицу добавим столбец «Время окончания процесса» и запишем туда длительности независимых процессов.
Далее рассчитаем время выполнения оставшихся процессов:
f(3) = 3 + max(f(1), f(2)) = 3 + 6 = 9;
f(5) = 4 + max(f(2), f(3)) = 4 + 9 = 13;
f(6) = 9 + max(f(4), f(5)) = 9 + 13 = 22;
f(8) = 5 + f(7) = 5 + 3 = 8;
f(9) = 2 + f(6) = 2 + 22 = 24;
f(10) = 6 + f(4) = 6 + 7 = 13;
f(11) = 2 + max(f(5), f(6)) = 2 + 22 = 24;
f(12) = 7 + max(f(7), f(8)) = 7 + 8 = 15;
f(14) = 3 + f(5) = 3 + 13 = 16;
f(15) = 8 + max(f(3), f(4)) = 8 + 9 = 17.
В результате получим следующую таблицу:
Нарисуем время выполняемых процессов:
Сдвинем независимые процессы так, чтобы выполнялось максимальное количество процессов одновременно:
Максимальное количество миллисекунд, когда одновременно может выполниться максимальное количество процессов равно - 2
Ответ: 2.