Задание 22 ЕГЭ: минимальное время выполнения всех процессов

Минимальное время выполнения процессов. Тема номера — параллельные процессы. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

В файле 22.xlsx содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Приостановка выполнения процесса не допускается.

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

Определите, на какое наибольшее время (в мс) можно увеличить время выполнения процесса с ID 16 так, чтобы минимальное время завершения всей совокупности процессов не изменилось. Все независимые друг от друга процессы могут выполняться параллельно, остальные процессы начинаются в самое раннее допустимое время.

Типовой пример организации данных в файле

Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс; время выполнения процесса 2 можно увеличить не более чем на 4 мс.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Скачать файл к примеру

Решение

Процесс может начаться, только когда завершатся все процессы, от которых он зависит, поэтому время его окончания = максимум из времён окончания этих процессов (0, если их нет) плюс его длительность. Считаем его рекурсией с запоминанием (порядок строк в таблице не важен). Процесс длительностью t, заканчивающийся на мс E, занимает миллисекунды E − t + 1 … E. Проще всего проверить напрямую: удлиняем процесс на 1, 2, 3, … мс, каждый раз пересчитывая расписание (сбрасываем кеш), пока общее время не вырастет.

Ответ: 52.

from functools import lru_cache
from openpyxl import load_workbook

ws = load_workbook("22.xlsx").active
dur, deps = {}, {}
for pid, t, d in ws.iter_rows(min_row=2, values_only=True):
    if pid is None:
        continue
    dur[pid] = t
    deps[pid] = [int(x) for x in str(d).split(";") if int(x) != 0]

@lru_cache(None)
def end(p):                     # мс, на которой процесс заканчивается
    return max((end(q) for q in deps[p]), default=0) + dur[p]

start = {p: end(p) - dur[p] for p in dur}   # процесс занимает мс start + 1 … end

k = 16
total = max(end(p) for p in dur)
t0, best = dur[k], 0
for d in range(1, total + 1):
    dur[k] = t0 + d
    end.cache_clear()          # длительность изменилась — пересчитываем
    if max(end(p) for p in dur) > total:
        break
    best = d
print(best)

Решить такую задачу — новый вариант с проверкой