Параллельные процессы: минимальное общее время
Условие
В таблице приведены сведения о процессах, которые могут выполняться параллельно (данные даны прямо в условии, в мини-версии вместо файла). Для каждого процесса B указаны его идентификатор (ID), время выполнения в миллисекундах и идентификаторы процессов A, от которых он зависит. Процесс B может начаться только после завершения всех процессов A, от которых он зависит; если процесс ни от чего не зависит, в последнем столбце записан 0. Независимые процессы могут выполняться одновременно, количество одновременно выполняемых процессов не ограничено. Временем на переключение между процессами можно пренебречь.
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(-ов) A |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 5 | 1 |
| 4 | 2 | 1; 2 |
| 5 | 6 | 3 |
| 6 | 3 | 4 |
| 7 | 4 | 5; 6 |
| 8 | 2 | 6 |
Определите минимальное время (в мс), через которое завершится выполнение всех процессов.