Задание 22 ЕГЭ по информатике: независимые процессы и критический путь

Рассчитайте минимальное время завершения группы процессов с зависимостями при неограниченном числе исполнителей.

Следующая задача в кабинете

Проверьте ответ здесь. Появится кнопка к другим заданиям этого номера.

К упражнениям
Скачать 22-processy.txt

Длительности в условных единицах времени. В ответе одно целое число.

Если два процесса длятся 4 и 6 единиц, а затем оба нужны процессу длительностью 3, ответ 9.

Задания

1Авторская задача

Каждая строка файла имеет формат «ID;длительность;ID предшественников». Предшественники разделены запятыми, прочерк означает, что их нет. Процесс может начаться только после завершения всех предшественников. Любые независимые процессы разрешено выполнять параллельно. За какое минимальное время завершатся все процессы?

Решение

Находим раннее завершение каждого процесса. Его ранний старт равен максимуму времени завершения предшественников. Задача ациклична, поэтому динамика или рекурсия с кешем проходит граф за линейное время.

from functools import lru_cache
from pathlib import Path

data = {}
for line in Path("22-processy.txt").read_text().splitlines():
    number, duration, dependencies = line.split(";")
    parent = [] if dependencies == "-" else list(map(int, dependencies.split(",")))
    data[int(number)] = int(duration), parent

@lru_cache(None)
def finish(number):
    duration, parent = data[number]
    return duration + max((finish(p) for p in parent), default=0)

print(max(map(finish, data)))

Дальше по теме

Источники