Решение: Параллельное выполнение процессов
В прилагаемом файле содержится таблица вычислительных процессов: для каждого процесса указаны его идентификатор, время выполнения и идентификаторы процессов, от которых он зависит. Независимые процессы могут выполняться параллельно, а зависимые — только последовательно.
Определите максимальную продолжительность отрезка времени в миллисекундах, в течение которого возможно одновременное выполнение максимального количества процессов. Приостановка выполнения процессов не допускается.
Решение по шагам
4 шагаПо данным файла для каждого процесса определяем время начала. Если процесс зависит от нескольких процессов, его запуск возможен после завершения самого позднего из них.
$$t_{start}(B)=\max_{A\in Dependencies(B)}(t_{start}(A)+t(A))$$Для каждого процесса записываем интервал его выполнения $[t_{start}, t_{start}+t]$ и объединяем все моменты начала и окончания процессов.
На каждом получившемся промежутке подсчитываем количество одновременно выполняющихся процессов.
Находим максимальное количество одновременно выполняющихся процессов и среди промежутков с этим количеством выбираем самый длинный.
Где здесь ошибаются
Считать зависимые процессы выполняющимися одновременно.
Начинать процесс сразу после завершения только одной из его зависимостей.
Искать общую продолжительность выполнения всех процессов вместо длины промежутка с максимальным параллелизмом.
Не учитывать моменты окончания процессов как границы интервалов.