В файле содержится информация о совокупности N вычислительных...

Задание:

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно.
Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение четырёх процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

Примечание: файлы в архиве с демоверсией ЕГЭ-2024 по информатике

Решение:

Построим диаграмму Ганта, где каждый процесс будет начинаться в самое раннее возможное время с учетом зависимостей.

Заметим, что имеем три независимые группы процессов: 1-8 процессы, 9 и 11 процессы, 10 и 12 процессы. Также заметим, что при выполнении 1-8 процессов не может выполняться больше двух процессов параллельно, для 9+11 и 10+12 – не более одного процесса. То есть 4 процесса может выполняться только при параллельном выполнении в первой группе 2 процессов и оставшихся двух групп процессов. Отрезок времени максимальной длины, когда в первой группе может выполняться два процесса одновременно - 7 мс (на диаграмме 10-16 мс). Время выполнения процессов 9 и 10 превышают этот показатель. Следовательно, ответ 7 мс.

Ответ: 7

Источник: Информатика с Джобсом | ЕГЭ