ЕГЭ · ЗАДАНИЕ 22
Параллельные процессы · практика 15
В файле указаны ID процесса, его время и ID процессов-предшественников (0 — зависимостей нет). Независимые процессы выполняются параллельно, процессоров неограниченно много. Каждый процесс стартует сразу после завершения всех предшественников. Найдите минимальное время завершения всех процессов.
Учебная модель Академии С для проверки приёма. Не выдаётся за задание реального экзамена.
Файлы к заданию
ege-22-checkpoint-7.txtИсточник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 36
Решение по шагам
- Процессоры не ограничены, поэтому независимые процессы стартуют вместе в момент 0. Складывать длительности всех процессов нельзя.
- Для каждого процесса начало = максимальное время окончания его предшественников. Конец = начало + собственная длительность.
- После расчёта всей таблицы берём максимальное время окончания: 36.
| ID | Длительность | Зависит от | Начало | Конец |
|---|---|---|---|---|
| 1 | 9 | 0 | 0 | 9 |
| 2 | 8 | 0 | 0 | 8 |
| 3 | 4 | 1 | 9 | 13 |
| 4 | 8 | 1,2 | 9 | 17 |
| 5 | 5 | 2 | 8 | 13 |
| 6 | 10 | 3,4 | 17 | 27 |
| 7 | 10 | 4,5 | 17 | 27 |
| 8 | 9 | 6,7 | 27 | 36 |
Проверка на Python
from functools import lru_cache
rows = [line.strip().split(";") for line in open("ege-22-checkpoint-7.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))