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