22. Вычислительные процессы: Это 3 процесса (за это время завершатся процессы 1, 2 и 4)
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы $A$ и $B$ могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение $0$.
Типовой пример организации данных в файле:
| ID процесса $B$ | Время выполнения процесса $B$ (мс) | ID процесса(ов) $A$ |
|---|---|---|
| $1$ | $3$ | $0$ |
| $2$ | $4$ | $1$ |
| $3$ | $2$ | $2$; $4$ |
| $4$ | $5$ | $0$ |
| $5$ | $8$ | $1$; $4$ |
Определите максимальное количество процессов, которые могут быть завершены за первые $17$ мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с $1$.
Например, для приведённой таблицы найдём количество процессов, которые могут быть завершены за первые $7$ мс. Это $3$ процесса (за это время завершатся процессы $1$, $2$ и $4$).
Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $106$, $113$ и $124$ завершатся на $2$, $5$ и $6$ мс соответственно. Процесс $114$ зависит от $106$, значит завершится на $2+3=5$ мс. Процесс $110$ зависит от $124$ и $106$: позже заканчивается $124$ (на $6$ мс), поэтому $110$ завершится на $6+2=8$ мс. От процесса $110$ зависят сразу три процесса — $103$, $116$ и $122$, и все они завершатся на $8+6=14$ мс.
Процесс $101$ зависит от $106$ и $122$, позже заканчивается $122$, значит $101$ завершится на $14+1=15$ мс; процесс $111$ зависит от $116$ и завершится на $14+1=15$ мс. Процесс $107$ зависит от $116$ и выполнится на $14+3=17$ мс, а процесс $121$ зависит от $106$ и $116$ — позже заканчивается $116$, поэтому $121$ тоже выполнится на $14+3=17$ мс. Все остальные процессы завершаются позже: ближайшие из них, $105$ и $125$, лишь на $18$ мс.
Таким образом, за первые $17$ мс успевают завершиться процессы $106$, $113$, $114$, $124$, $110$, $103$, $116$, $122$, $101$, $111$, $107$ и $121$ — всего $12$ процессов.
| Время, мс | ID процесса |
|---|---|
| $2$ | $106$ |
| $5$ | $113$, $114$ |
| $6$ | $124$ |
| $8$ | $110$ |
| $14$ | $103$, $116$, $122$ |
| $15$ | $101$, $111$ |
| $17$ | $107$, $121$ |
| $18$ | $105$, $125$ |
| $19$ | $118$ |
| $20$ | $112$, $119$ |
| $22$ | $104$, $120$ |
| $23$ | $102$ |
| $24$ | $109$ |
| $25$ | $108$ |
| $26$ | $117$ |
| $28$ | $123$ |
| $29$ | $115$ |
Приведём другое решение на языке Python.
import pandas as pd
from functools import lru_cache
df = pd.read_excel('22-02.ods', engine='odf', header=None, skiprows=1)
t, dep = {}, {}
for _, row in df.iterrows():
pid = int(row[0])
t[pid] = int(row[1])
s = str(row[2]).strip()
dep[pid] = [] if s == '0' else [int(x) for x in s.split(';')]
@lru_cache(None)
def finish(p): # момент завершения процесса p
return t[p] + max([finish(d) for d in dep[p]], default=0)
print(sum(1 for p in t if finish(p) <= 17)) # 12
Процесс не может стартовать раньше, чем закончатся все, от которых он зависит, но и ждать дольше незачем — значит время его завершения равно собственной длительности плюс максимум по временам завершения предшественников. Рекурсия с кэшированием считает это за один проход, а дальше остаётся сосчитать процессы, у которых время завершения не превышает $17$.