Параллельное выполнение процессов
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы $A$ и $B$ могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите максимальное количество процессов, которые могут быть завершены за первые 17 мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Условие как в банке ФИПИ — открыть и сверить
| |||||||||||||||||||||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Для каждого процесса определите самое раннее время его запуска с учётом завершения всех процессов-зависимостей.
2Наводящая — какие числа считатьуровень 2 из 3
Если процесс выполняется $t$ миллисекунд и запускается в момент $s$, он завершается в момент $s+t$. Процесс можно запустить после завершения всех его предшественников.
3Прямая — фактически решениеуровень 3 из 3
Обработайте процессы в порядке зависимостей, вычислите времена их завершения и подсчитайте процессы, для которых время завершения не превышает 17 мс. Получается 12 процессов.