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)))