ЕГЭ · ЗАДАНИЕ 22
Параллельные процессы · практика 13
В файле указаны ID процесса, его время и ID процессов-предшественников (0 — зависимостей нет). Независимые процессы выполняются параллельно, процессоров неограниченно много. Каждый процесс стартует сразу после завершения всех предшественников. Найдите минимальное время завершения всех процессов.
Учебная модель Академии С для проверки приёма. Не выдаётся за задание реального экзамена.
Файлы к заданию
ege-22-checkpoint-5.txtИсточник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 22
Решение по шагам
- Процессоры не ограничены, поэтому независимые процессы стартуют вместе в момент 0. Складывать длительности всех процессов нельзя.
- Для каждого процесса начало = максимальное время окончания его предшественников. Конец = начало + собственная длительность.
- После расчёта всей таблицы берём максимальное время окончания: 22.
| ID | Длительность | Зависит от | Начало | Конец |
|---|---|---|---|---|
| 1 | 2 | 0 | 0 | 2 |
| 2 | 3 | 0 | 0 | 3 |
| 3 | 6 | 1 | 2 | 8 |
| 4 | 5 | 1,2 | 3 | 8 |
| 5 | 7 | 2 | 3 | 10 |
| 6 | 3 | 3,4 | 8 | 11 |
| 7 | 4 | 4,5 | 10 | 14 |
| 8 | 8 | 6,7 | 14 | 22 |
Проверка на Python
from functools import lru_cache
rows = [line.strip().split(";") for line in open("ege-22-checkpoint-5.txt")][1:]
data = {int(i): (int(t), list(map(int, deps.split(",")))) for i, t, deps in rows}
@lru_cache(None)
def end(i):
if i == 0: return 0
duration, deps = data[i]
return duration + max(end(j) for j in deps)
print(max(end(i) for i in data))