Шешімі: Параллельное выполнение процессов
В прилагаемом файле содержится таблица процессов: для каждого процесса указаны его идентификатор, время выполнения в миллисекундах и идентификаторы процессов, от которых он зависит. Определите максимальное количество процессов, которые параллельно выполняются на 7-й миллисекунде, если каждый процесс начинается в самое раннее допустимое время.
Шешімін қадамдап көрсету
4 қадамДля каждого процесса по таблице из файла вычисляем самое раннее время начала. Если процесс не имеет зависимостей, он начинается с 1-й миллисекунды. Для зависимого процесса начало определяется окончанием последнего из процессов-зависимостей.
$$start(B)=\max\limits_{A\in dependencies(B)}(start(A)+duration(A))$$Для каждого процесса строим интервал выполнения: если он начинается на миллисекунде s и длится d миллисекунд, то выполняется на миллисекундах s, s+1, \ldots, s+d-1.
$$finish(B)=start(B)+duration(B)-1$$Отбираем процессы, для которых выполняется условие start(B)\leq 7\leq finish(B), и подсчитываем их количество.
На 7-й миллисекунде одновременно выполняются 8 процессов.
Где здесь ошибаются
Считать зависимый процесс доступным сразу после начала процесса-предшественника, а не после его завершения.
Учитывать миллисекунду окончания процесса как дополнительную миллисекунду выполнения.
Начинать нумерацию миллисекунд с нуля вместо единицы.