22. Вычислительные процессы: все задания

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $106$, $107$ и $112$ завершатся на $3$, $5$ и $6$ мс соответственно. Процесс $105$ зависит от $107$, значит завершится на $5+1=6$ мс. Процесс $102$ тоже зависит от $107$ и завершится на $5+5=10$ мс, а процесс $119$ зависит от $112$ и $106$: позже заканчивается $112$ (на $6$ мс), поэтому $119$ завершится на $6+4=10$ мс.

Дальше процесс $101$ зависит от $102$ и $119$, оба заканчиваются на $10$ мс, значит $101$ завершится на $10+1=11$ мс. Процесс $109$ зависит от $112$ и завершится на $6+5=11$ мс, процесс $118$ зависит от $101$ и $109$ — оба на $11$ мс, поэтому $118$ завершится на $11+3=14$ мс. Процесс $110$ зависит от $118$ и $119$, позже заканчивается $118$, значит $110$ завершится на $14+6=20$ мс. Процесс $111$ зависит от $110$ и завершится на $20+4=24$ мс, а процесс $117$ зависит от $111$, следовательно, выполнится на $24+5=29$ мс.

Таким образом, вся совокупность процессов завершится на $29$ мс.

Приведём другое решение на языке Python.

import sys

d = {'0': 0}
for elem in sys.stdin:
    num, dur, *subs = elem.replace(';', ' ').split()
    d[num] = max([d[i] for i in subs]) + int(dur)

print(max(d.values()))

Запустив программу, вводим данные из таблицы построчно, цифры в строках разделяем пробелом. Закончив ввод всех строк таблицы, необходимо нажать CTRL+D.

Примечание. Способ работает при условии, что процессы в файле идут в таком порядке, что каждый встречается уже после всех тех, от которых он зависит. Если порядок произвольный, надёжнее читать файл целиком и считать время завершения рекурсией с кэшированием:

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-01.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(max(finish(p) for p in t))   # 29

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $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$ процессов.

Приведём другое решение на языке 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$.

Здесь мало знать время завершения — нужен весь отрезок работы каждого процесса. Процесс стартует в самое раннее допустимое время, то есть сразу после того, как закончится последний из тех, от которых он зависит. Если процесс заканчивается на мс $f$ и длится $d$ мс, то занят он миллисекундами с $f-d+1$ по $f$. Процесс выполняется на $23$-й мс, если $f-d+1 \le 23 \le f$.

Считаем времена завершения по цепочкам. Независимые процессы $102$, $103$ и $123$ занимают мс $1$–$6$, $1$–$6$ и $1$ соответственно. Процесс $106$ зависит от $103$, значит идёт с $7$ по $9$ мс, а зависящий от него $107$ — с $10$ по $12$ мс. Процесс $112$ зависит от $103$ и $123$, стартует после $6$ мс и работает с $7$ по $12$ мс. Процесс $117$ зависит от $103$ и $112$, позже заканчивается $112$, поэтому $117$ идёт с $13$ по $17$ мс. Наконец, процесс $109$ зависит от $117$ и $103$: он стартует после $17$ мс и работает с $18$ по $23$ мс — именно он захватывает $23$-ю миллисекунду.

Проверим остальные. Все процессы, заканчивающиеся раньше $23$ мс, отпадают сразу. Из тех, что заканчиваются позже, процесс $105$ занимает мс $24$–$25$, процесс $111$ — мс $26$–$27$, процесс $124$ — мс $26$–$30$. Ни один из них до $23$-й миллисекунды не дотягивается, потому что все они зависят от $109$ и ждут его окончания.

Таким образом, на $23$-й мс выполняется только один процесс — $109$.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-03.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)

# процесс занимает мс с finish-t+1 по finish
print(sum(1 for p in t if finish(p) - t[p] < 23 <= finish(p)))   # 1

Условие finish(p) - t[p] < 23 означает, что процесс успел стартовать до конца $23$-й миллисекунды, а 23 <= finish(p) — что он к этому моменту ещё не закончился. Вся совокупность процессов в этом файле завершается на $30$ мс.

Здесь мало знать время завершения — нужен весь отрезок работы каждого процесса. Процесс стартует в самое раннее допустимое время, то есть сразу после того, как закончится последний из тех, от которых он зависит. Если процесс заканчивается на мс $f$ и длится $d$ мс, то занят он миллисекундами с $f-d+1$ по $f$. Процесс выполняется на $16$-й мс, если $f-d+1 \le 16 \le f$.

Считаем по цепочкам. Независимые процессы $111$, $122$ и $114$ занимают мс $1$, $1$ и $1$–$4$. Процесс $109$ зависит от $111$ и идёт с $2$ по $5$ мс. Процесс $103$ зависит от $114$ и $111$, стартует после $4$ мс и работает с $5$ по $10$ мс. От него зависят сразу несколько процессов: $101$ и $102$ занимают мс $11$–$16$, а $115$ — мс $11$–$15$.

Дальше процессы, стартующие ровно на $16$-й мс. Процесс $116$ зависит от $109$ и $115$, позже заканчивается $115$ (на $15$ мс), поэтому $116$ идёт с $16$ по $17$ мс. Процесс $117$ зависит от $103$ и $115$ и по той же причине занимает мс $16$–$19$. Процесс $123$ зависит от $111$ и $115$, тоже стартует после $15$ мс и работает с $16$ по $21$ мс.

Ещё два процесса захватывают $16$-ю мс, начавшись раньше. Процесс $124$ зависит от $109$ и $103$ и занимает мс $11$–$13$, процесс $121$ зависит от $109$ и занимает мс $6$–$11$. Оба они предшествуют процессам $104$ и $108$: те стартуют после $13$ мс, поэтому $104$ идёт с $14$ по $17$ мс, а $108$ — с $14$ по $19$ мс.

Таким образом, на $16$-й мс параллельно выполняются процессы $101$, $102$, $104$, $108$, $116$, $117$ и $123$ — всего $7$ процессов.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-04.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)

# процесс занимает мс с finish-t+1 по finish
print(sum(1 for p in t if finish(p) - t[p] < 16 <= finish(p)))   # 7

Условие finish(p) - t[p] < 16 означает, что процесс успел стартовать до конца $16$-й миллисекунды, а 16 <= finish(p) — что он к этому моменту ещё не закончился. Вся совокупность процессов в этом файле завершается на $27$ мс.

Составим таблицу, на какой мс завершится каждый из процессов, и будем накапливать их количество. Искомое время — это момент завершения $22$-го по счёту процесса.

Независимые процессы $101$, $108$ и $112$ завершаются уже на $1$ мс — это сразу три процесса. Процесс $120$ зависит от $112$ и $108$ и завершается на $1+2=3$ мс, процессы $107$ и $118$ — на $4$ мс, процесс $110$ — на $5$ мс. К шестой миллисекунде добавляются $102$ и $125$, и завершённых становится $9$.

Дальше: процесс $113$ зависит от $120$ и завершается на $3+5=8$ мс, процесс $106$ зависит от $102$ и завершается на $6+4=10$ мс. На $11$ мс заканчиваются $103$ и $109$, на $12$ мс — $122$, на $13$ мс — $124$, на $14$ мс — $111$, на $15$ мс — $116$, на $16$ мс — $117$. К этому моменту завершено $18$ процессов.

На $17$ мс заканчиваются сразу два процесса — $105$ и $123$, всего становится $20$. На $20$ мс завершается $114$ — двадцать первый. И на $21$ мс завершается процесс $119$, который зависит от $120$ и $117$: позже заканчивается $117$ (на $16$ мс), поэтому $119$ идёт до $16+5=21$ мс. Это и есть двадцать второй завершённый процесс.

Оставшиеся три процесса заканчиваются заметно позже: $115$ на $25$ мс, $104$ на $30$ мс и $121$ на $31$ мс.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-05.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)

times = sorted(finish(p) for p in t)
print(times[21])   # 21 — время завершения 22-го по счёту процесса

Отсортировав времена завершения по возрастанию, достаточно взять элемент с индексом $21$ — это и есть момент, когда завершится двадцать второй процесс.

Составим таблицу, на какой мс завершится каждый из процессов, и будем накапливать их количество. Искомое время — момент завершения $17$-го по счёту процесса.

Независимые процессы $121$, $106$ и $112$ завершаются на $2$, $3$ и $4$ мс. Процесс $125$ зависит от $112$ и завершается на $4+1=5$ мс. На $6$ мс заканчиваются сразу три процесса: $103$ (зависит от $125$), а также $116$ и $122$ (оба зависят от $112$) — всего завершено $7$.

Дальше процессы $105$ и $115$ зависят от $121$ и завершаются на $2+6=8$ мс, их становится $9$. На $9$ мс заканчиваются $108$ (зависит от $106$ и $112$, стартует после $4$ мс), $111$ (зависит от $125$ и $121$, стартует после $5$ мс) и $102$ (зависит от $115$ и $106$, стартует после $8$ мс) — всего $12$.

На $11$ мс завершаются $109$ и $124$, завершённых становится $14$. И наконец на $12$ мс заканчиваются сразу три процесса: $107$ (зависит от $115$ и $109$), $117$ (зависит от $115$) и $120$ (зависит от $109$ и $115$). Все они стартуют после $11$ мс либо после $8$ мс, и вместе доводят счёт до $17$.

Значит минимальное время, за которое завершатся $17$ процессов, равно $12$ мс.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-06.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)

times = sorted(finish(p) for p in t)
print(times[16])   # 12 — время завершения 17-го по счёту процесса

Отсортировав времена завершения по возрастанию, достаточно взять элемент с индексом $16$ — это и есть момент, когда завершится семнадцатый процесс. Обратите внимание, что на $12$-й мс заканчиваются сразу три процесса, поэтому счёт перескакивает с $14$ сразу до $17$.

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $1$, $2$, $4$ и $12$ завершатся на $20$, $26$, $28$ и $29$ мс соответственно.

Процесс $8$ зависит от $1$, значит завершится на $20+32=52$ мс. Процесс $5$ зависит от $2$ и завершится на $26+29=55$ мс. Процесс $7$ зависит от $5$, поэтому закончится на $55+31=86$ мс, а процесс $10$ зависит от $7$ и завершится на $86+34=120$ мс.

Процесс $13$ зависит от $10$ и $12$: позже заканчивается $10$ (на $120$ мс), значит $13$ завершится на $120+32=152$ мс. От него зависят два процесса — $3$ заканчивается на $152+22=174$ мс, а $17$ на $152+36=188$ мс.

Процесс $9$ зависит от $3$ и $4$, позже заканчивается $3$, поэтому $9$ завершится на $174+28=202$ мс. Дальше процесс $11$ зависит от $9$ и завершится на $202+30=232$ мс, а процесс $15$ тоже зависит от $9$ и завершится на $202+39=241$ мс.

Процесс $14$ зависит от $11$ и $15$: позже заканчивается $15$ (на $241$ мс), значит $14$ завершится на $241+33=274$ мс. Наконец, процесс $16$ зависит от $14$ и $15$, стартует после $274$ мс и завершается на $274+33=307$ мс. Для сравнения, процесс $6$ зависит от $5$, $7$, $8$ и $15$ и заканчивается лишь на $241+25=266$ мс — раньше, чем $16$.

Таким образом, вся совокупность процессов завершится на $307$ мс.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-07.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(max(finish(p) for p in t))   # 307

Процесс не может стартовать раньше, чем закончатся все, от которых он зависит, но и ждать дольше незачем — значит время его завершения равно собственной длительности плюс максимум по временам завершения предшественников. Ответ — максимум по всем процессам, потому что вся совокупность закончится тогда, когда закончится самый поздний из них.

Нужен отрезок работы каждого процесса. Процесс стартует сразу после того, как закончится последний из тех, от которых он зависит. Если процесс заканчивается на мс $f$ и длится $d$ мс, то занят он миллисекундами с $f-d+1$ по $f$. Процесс выполняется на $6$-й мс, если $f-d+1 \le 6 \le f$.

Независимые процессы $6$, $25$ и $17$ занимают мс $1$, $1$–$2$ и $1$–$4$ соответственно. Процесс $2$ зависит от $6$ и $25$, стартует после $2$ мс и работает с $3$ по $4$ мс; процесс $4$ зависит от $25$ и тоже занимает мс $3$–$4$. Процесс $7$ зависит от $25$, стартует после $2$ мс и работает с $3$ по $7$ мс — он захватывает шестую миллисекунду.

Дальше идут процессы, стартующие после $4$ мс. Процесс $8$ зависит от $17$ и $25$, позже заканчивается $17$ (на $4$ мс), поэтому $8$ занимает мс $5$–$10$. Процесс $14$ зависит от $4$ и занимает мс $5$–$9$. Процесс $23$ зависит от $17$ и занимает мс $5$–$9$. Процесс $20$ тоже зависит от $17$ и занимает мс $5$–$7$. Наконец, процесс $18$ зависит от $2$, $17$ и $4$ — все они заканчиваются на $4$ мс, значит $18$ работает с $5$ по $7$ мс.

Все эти пять процессов плюс процесс $7$ и дают ответ. Остальные либо заканчиваются раньше шестой миллисекунды ($6$, $25$, $17$, $2$, $4$), либо стартуют позже: ближайшие из них, $10$, $16$ и $22$, начинаются только на $8$-й мс.

Таким образом, на $6$-й мс параллельно выполняются процессы $7$, $8$, $14$, $18$, $20$ и $23$ — всего $6$ процессов.

Ответ: $6$.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-08.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)

# процесс занимает мс с finish-t+1 по finish
print(sum(1 for p in t if finish(p) - t[p] < 6 <= finish(p)))   # 6

Условие finish(p) - t[p] < 6 означает, что процесс успел стартовать до конца $6$-й миллисекунды, а 6 <= finish(p) — что он к этому моменту ещё не закончился. Вся совокупность процессов в этом файле завершается на $26$ мс.

Сначала расписываем отрезок работы каждого процесса: он стартует сразу после окончания последнего из тех, от которых зависит, и занимает миллисекунды с $f-d+1$ по $f$, где $f$ — момент завершения, а $d$ — длительность.

Независимые процессы $101$, $102$ и $110$ занимают мс $1$–$14$, $1$–$3$ и $1$–$8$. Процесс $104$ зависит от $102$ и работает с $4$ по $14$ мс. Процессы $111$ и $112$ зависят от $110$ и стартуют после $8$ мс: $111$ занимает мс $9$–$24$, $112$ — мс $9$–$16$. Процесс $103$ зависит от $101$ и $102$, позже заканчивается $101$ (на $14$ мс), поэтому $103$ занимает единственную $15$-ю мс. От него зависят $105$ (мс $16$–$28$) и $106$ (мс $16$–$20$), а от $106$ — процесс $107$ (мс $21$–$23$). Процесс $113$ зависит от $112$ и занимает мс $17$–$30$. Наконец, $108$ работает на $29$-й мс, а $109$ — на мс $30$–$31$.

Теперь считаем, сколько процессов идёт одновременно на каждой миллисекунде. Максимум равен $4$, и достигается он дважды. Первый раз — на мс с $9$ по $14$, когда параллельно идут $101$, $104$, $111$ и $112$: это отрезок длиной $6$ мс. Затем на $15$-й мс остаются только $103$, $111$ и $112$, то есть три процесса, и цепочка обрывается. Второй раз четвёрка набирается с $16$-й мс — работают $105$, $106$, $111$ и $112$ — и держится до $23$-й мс включительно, хотя состав по ходу меняется: с $17$-й мс вместо $112$ подключается $113$, а с $21$-й мс вместо $106$ идёт $107$. Это отрезок с $16$ по $23$ мс длиной $8$ мс. На $24$-й мс процесс $107$ уже закончился, и параллельных остаётся три.

Таким образом, максимальное количество одновременно выполняемых процессов равно $4$, а самый длинный отрезок, на котором это количество держится, длится $8$ мс.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-09.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)

T = max(finish(p) for p in t)
cnt = [0] * (T + 2)                   # сколько процессов идёт на каждой мс
for p in t:
    for ms in range(finish(p) - t[p] + 1, finish(p) + 1):
        cnt[ms] += 1

M = max(cnt[1:T+1])                   # максимум одновременных процессов

best = cur = 0                        # самая длинная цепочка мс со значением M
for ms in range(1, T + 1):
    cur = cur + 1 if cnt[ms] == M else 0
    best = max(best, cur)

print(best)   # 8

Обратите внимание: спрашивается не про конкретный набор процессов, а про количество. Состав четвёрки внутри отрезка с $16$ по $23$ мс меняется трижды, но одновременно работающих всё время ровно четыре, поэтому весь отрезок считается целиком.

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $2$, $1$, $4$ и $12$ завершатся на $19$, $20$, $23$ и $31$ мс соответственно.

Процесс $5$ зависит от $2$, значит завершится на $19+24=43$ мс. Процесс $8$ зависит от $1$ и завершится на $20+27=47$ мс. Дальше сразу два процесса заканчиваются на $69$ мс: процесс $3$ зависит от $8$ ($47+22=69$), а процесс $7$ зависит от $5$ ($43+26=69$).

Процесс $10$ зависит от $7$ и завершится на $69+29=98$ мс. Процесс $9$ зависит от $3$ и $4$, позже заканчивается $3$ (на $69$ мс), поэтому $9$ завершится на $69+31=100$ мс. От него зависят $11$ (на $100+32=132$ мс) и $15$ (на $100+34=134$ мс).

Процесс $14$ зависит от $10$ и $12$: позже заканчивается $10$ (на $98$ мс), значит $14$ завершится на $98+38=136$ мс. Процесс $13$ зависит от $11$ и $15$, позже заканчивается $15$, поэтому $13$ завершится на $134+32=166$ мс, а зависящий от него процесс $16$ — на $166+43=209$ мс.

Наконец, процесс $17$ зависит от $14$ и $16$: позже заканчивается $16$ (на $209$ мс), значит $17$ завершится на $209+55=264$ мс. Для сравнения, процесс $6$ зависит от $5$, $7$, $8$ и $14$ и заканчивается лишь на $136+18=154$ мс — заметно раньше.

Таким образом, вся совокупность процессов завершится на $264$ мс.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-10.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(max(finish(p) for p in t))   # 264

Процесс не может стартовать раньше, чем закончатся все, от которых он зависит, но и ждать дольше незачем — значит время его завершения равно собственной длительности плюс максимум по временам завершения предшественников. Ответ — максимум по всем процессам, потому что вся совокупность закончится тогда, когда закончится самый поздний из них.

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $7$, $1$, $2$, $11$, $4$ и $14$ завершатся на $16$, $17$, $18$, $21$, $24$ и $24$ мс соответственно.

Процесс $3$ зависит от $1$ и $2$: позже заканчивается $2$ (на $18$ мс), значит $3$ завершится на $18+19=37$ мс. Дальше на $56$ мс заканчиваются сразу два процесса: $5$ зависит от $1$ и $3$ и стартует после $37$ мс, а $6$ зависит от $2$, $3$ и $4$ — тоже после $37$ мс, поскольку $3$ заканчивается позже остальных.

Процесс $9$ зависит от $2$ и $6$, стартует после $56$ мс и завершится на $56+10=66$ мс. Процесс $8$ зависит от $3$, $5$, $6$ и $7$: позже всех заканчиваются $5$ и $6$ (на $56$ мс), поэтому $8$ завершится на $56+15=71$ мс. Процесс $10$ зависит от $3$, $6$ и $9$, стартует после $66$ мс и завершится на $66+11=77$ мс.

Процесс $12$ зависит от $7$, $8$ и $11$, позже заканчивается $8$, значит $12$ завершится на $71+22=93$ мс. Процесс $13$ зависит от $4$, $5$, $9$ и $10$: позже всех заканчивается $10$ (на $77$ мс), поэтому $13$ завершится на $77+29=106$ мс.

Процесс $15$ зависит от $12$ и $13$, позже заканчивается $13$, значит $15$ завершится на $106+18=124$ мс. От него зависят два последних процесса: $16$ (зависит от $14$ и $15$) завершится на $124+19=143$ мс, а $17$ (зависит от $10$, $11$ и $15$) — на $124+24=148$ мс.

Таким образом, вся совокупность процессов завершится на $148$ мс.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-11.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]).replace(' ', '').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(max(finish(p) for p in t))   # 148

Обратите внимание на разбор третьего столбца: в этом файле зависимости записаны неаккуратно — где-то «$1;2$», а где-то «$2; 3; 4$» с пробелами. Поэтому перед разбиением по «;» пробелы надо убрать, иначе int()споткнётся.

Условие «время окончания работы всех процессов минимально» означает, что каждый процесс стартует в самое раннее допустимое время — сразу после окончания последнего из тех, от которых он зависит. Расписываем отрезки: процесс, заканчивающийся на мс $f$ и длящийся $d$ мс, занят миллисекундами с $f-d+1$ по $f$.

Независимые процессы $101$, $107$ и $108$ занимают мс $1$–$7$, $1$–$10$ и $1$–$17$. Процессы $102$ и $103$ зависят от $101$ и стартуют после $7$ мс: $102$ занимает мс $8$–$23$, $103$ — мс $8$–$24$. Процессы $109$ и $111$ зависят от $108$ и стартуют после $17$ мс: $109$ занимает мс $18$–$27$, $111$ — мс $18$–$24$. Процесс $104$ зависит от $103$ и $107$, позже заканчивается $103$ (на $24$ мс), значит $104$ занимает мс $25$–$34$; от него зависят $105$ (мс $35$–$38$) и $106$ (мс $35$–$48$). Процесс $112$ зависит от $111$ и занимает мс $25$–$43$, а процесс $110$ зависит от $109$ и занимает мс $28$–$50$.

Теперь считаем, сколько процессов идёт одновременно на каждой миллисекунде. Максимум равен $4$, и достигается он трижды. С $8$ по $10$ мс работают $102$, $103$, $107$ и $108$ — отрезок в $3$ мс; на $11$-й мс процесс $107$ уже закончился. С $18$ по $23$ мс работают $102$, $103$, $109$ и $111$ — отрезок в $6$ мс; на $24$-й мс процесс $102$ закончился. С $35$ по $38$ мс работают $105$, $106$, $110$ и $112$ — отрезок в $4$ мс; на $39$-й мс заканчивается $105$.

Самый длинный из этих отрезков — с $18$ по $23$ мс, его продолжительность $6$ мс.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-12.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]).replace(' ', '').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)

T = max(finish(p) for p in t)
cnt = [0] * (T + 2)                   # сколько процессов идёт на каждой мс
for p in t:
    for ms in range(finish(p) - t[p] + 1, finish(p) + 1):
        cnt[ms] += 1

M = max(cnt[1:T+1])                   # максимум одновременных процессов

best = cur = 0                        # самая длинная цепочка мс со значением M
for ms in range(1, T + 1):
    cur = cur + 1 if cnt[ms] == M else 0
    best = max(best, cur)

print(best)   # 6

Спрашивается не про конкретный набор процессов, а про количество, поэтому важно только значение счётчика. Вся совокупность процессов в этом файле завершается на $50$ мс.

Нужен отрезок работы каждого процесса. Процесс стартует сразу после того, как закончится последний из тех, от которых он зависит, и занимает миллисекунды с $f-d+1$ по $f$, где $f$ — момент завершения, $d$ — длительность. Процесс выполняется на $7$-й мс, если $f-d+1 \le 7 \le f$.

Независимые процессы $17$, $22$ и $25$ занимают мс $1$–$2$, $1$–$4$ и $1$–$5$. От процесса $17$ зависят $7$ и $21$, оба стартуют после $2$ мс и занимают мс $3$–$8$ — они захватывают седьмую миллисекунду. От процесса $22$ зависят $12$, $18$ и $19$, все стартуют после $4$ мс: $12$ и $18$ занимают мс $5$–$10$, $19$ — мс $5$–$9$; все три тоже попадают на седьмую миллисекунду.

Дальше идут процессы, стартующие после $5$ мс. Процесс $11$ зависит от $25$ и занимает мс $6$–$11$, процесс $16$ зависит от $25$ и занимает мс $6$–$9$, процесс $15$ зависит от $17$ и $25$ (позже заканчивается $25$, на $5$ мс) и занимает мс $6$–$8$. Все три захватывают седьмую миллисекунду.

Итого восемь процессов. Остальные либо уже закончились к седьмой мс ($17$, $22$, $25$), либо стартуют позже: ближайшие из них — $3$, $24$ и $16$… точнее $3$ и $24$ начинаются только на $9$-й мс, а $8$ и $13$ — на $10$-й.

Таким образом, на $7$-й мс параллельно выполняются процессы $7$, $11$, $12$, $15$, $16$, $18$, $19$ и $21$ — всего $8$ процессов.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-13.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]).replace(' ', '').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)

# процесс занимает мс с finish-t+1 по finish
print(sum(1 for p in t if finish(p) - t[p] < 7 <= finish(p)))   # 8

Условие finish(p) - t[p] < 7 означает, что процесс успел стартовать до конца $7$-й миллисекунды, а 7 <= finish(p) — что он к этому моменту ещё не закончился. Вся совокупность процессов в этом файле завершается на $17$ мс.

Расписываем отрезок работы каждого процесса: он стартует сразу после окончания последнего из тех, от которых зависит, и занимает миллисекунды с $f-d+1$ по $f$, где $f$ — момент завершения, $d$ — длительность.

Независимые процессы $101$, $107$ и $108$ занимают мс $1$–$7$, $1$–$7$ и $1$–$18$. Процессы $102$ и $103$ зависят от $101$ и стартуют после $7$ мс: $102$ занимает мс $8$–$22$, $103$ — мс $8$–$23$. Процессы $109$ и $111$ зависят от $108$ и стартуют после $18$ мс: $109$ занимает мс $19$–$28$, $111$ — мс $19$–$25$. Процесс $104$ зависит от $103$ и $107$, позже заканчивается $103$ (на $23$ мс), значит $104$ занимает мс $24$–$33$; от него зависят $105$ (мс $34$–$46$) и $106$ (мс $34$–$37$). Процесс $112$ зависит от $111$ и занимает мс $26$–$29$, а процесс $110$ зависит от $109$ и занимает мс $29$–$47$.

Теперь считаем, сколько процессов идёт одновременно на каждой миллисекунде. На первых восемнадцати миллисекундах их всегда три. На $19$-й мс к процессам $102$ и $103$ добавляются $109$ и $111$, а $108$ как раз закончился — становится четыре. Столько же держится до $22$-й мс включительно, а на $23$-й мс процесс $102$ уже закончился, и остаётся три. Больше четырёх нигде не набирается: дальше по файлу счётчик опускается до трёх и двух.

Таким образом, максимальное количество одновременно выполняемых процессов равно $4$, и держится оно ровно на отрезке с $19$ по $22$ мс, то есть $4$ мс.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-14.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]).replace(' ', '').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)

T = max(finish(p) for p in t)
cnt = [0] * (T + 2)                   # сколько процессов идёт на каждой мс
for p in t:
    for ms in range(finish(p) - t[p] + 1, finish(p) + 1):
        cnt[ms] += 1

M = max(cnt[1:T+1])                   # максимум одновременных процессов

best = cur = 0                        # самая длинная цепочка мс со значением M
for ms in range(1, T + 1):
    cur = cur + 1 if cnt[ms] == M else 0
    best = max(best, cur)

print(best)   # 4

Здесь максимум достигается лишь в одном месте, поэтому и отрезок единственный. Вся совокупность процессов завершается на $47$ мс.

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $1$, $2$, $11$ и $4$ завершатся на $20$, $21$, $22$ и $25$ мс соответственно.

Процесс $8$ зависит от $1$, значит завершится на $20+23=43$ мс. Процесс $5$ зависит от $2$ и завершится на $21+27=48$ мс, а процесс $7$ зависит от $5$ и завершится на $48+20=68$ мс. От процесса $7$ зависят два процесса: $3$ заканчивается на $68+19=87$ мс, а $10$ — на $68+26=94$ мс.

Процесс $9$ зависит от $3$ и $4$: позже заканчивается $3$ (на $87$ мс), значит $9$ завершится на $87+18=105$ мс. От него зависят $12$ (на $105+21=126$ мс) и $15$ (на $105+27=132$ мс).

Процесс $13$ зависит от $10$ и $12$, позже заканчивается $12$, поэтому $13$ завершится на $126+24=150$ мс. Процесс $14$ зависит от $11$ и $15$, позже заканчивается $15$, значит $14$ завершится на $132+26=158$ мс. Процесс $16$ зависит от $13$ и завершится на $150+24=174$ мс.

Процесс $17$ зависит от $14$ и $16$: позже заканчивается $16$ (на $174$ мс), поэтому $17$ завершится на $174+26=200$ мс. Наконец, процесс $18$ зависит от $14$ и $17$, стартует после $200$ мс и завершается на $200+23=223$ мс. Для сравнения, процесс $6$ зависит от $5$, $7$, $8$ и $14$ и заканчивается на $158+24=182$ мс — раньше.

Таким образом, вся совокупность процессов завершится на $223$ мс.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-15-1.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]).replace(' ', '').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(max(finish(p) for p in t))   # 223

Процесс не может стартовать раньше, чем закончатся все, от которых он зависит, но и ждать дольше незачем — значит время его завершения равно собственной длительности плюс максимум по временам завершения предшественников. Ответ — максимум по всем процессам, потому что вся совокупность закончится тогда, когда закончится самый поздний из них.

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $1$, $2$ и $12$ завершатся на $3$, $4$ и $6$ мс соответственно.

Процесс $3$ зависит от $2$ и завершится на $4+1=5$ мс, процесс $19$ тоже зависит от $2$ и завершится на $6$ мс. Процесс $5$ зависит от $12$ и завершится на $6+1=7$ мс. Процесс $6$ зависит от $3$ и $12$: позже заканчивается $12$ (на $6$ мс), значит $6$ завершится на $6+6=12$ мс.

От процесса $6$ дальше зависит целая ветка. Процессы $11$, $17$ и $24$ завершаются на $14$ мс, процесс $20$ — на $15$ мс. Процесс $18$ зависит от $11$ и $2$, стартует после $14$ мс и завершается на $14+6=20$ мс. Процесс $9$ зависит от $3$, $17$ и $12$ и завершается на $14+6=20$ мс.

Процесс $8$ зависит от $20$, $6$ и $18$: позже заканчивается $18$ (на $20$ мс), значит $8$ завершится на $20+3=23$ мс. От него зависит $23$, который завершится на $23+2=25$ мс. Процесс $4$ зависит от $5$ и $18$ и завершится на $20+6=26$ мс.

Процесс $13$ зависит от $4$ и $23$: позже заканчивается $4$ (на $26$ мс), поэтому $13$ завершится на $26+3=29$ мс. И наконец, процесс $21$ зависит от $6$, $1$ и $13$, стартует после $29$ мс и завершается на $29+5=34$ мс. Для сравнения, вторая длинная ветка идёт через процесс $7$ ($28$ мс) и $16$ ($32$ мс) — она короче.

Таким образом, вся совокупность процессов завершится на $34$ мс.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-16.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]).replace(' ', '').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(max(finish(p) for p in t))   # 34

Процесс не может стартовать раньше, чем закончатся все, от которых он зависит, но и ждать дольше незачем — значит время его завершения равно собственной длительности плюс максимум по временам завершения предшественников. Ответ — максимум по всем процессам, потому что вся совокупность закончится тогда, когда закончится самый поздний из них.

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $2$, $1$ и $4$ завершатся на $3$, $8$ и $10$ мс соответственно.

Процесс $3$ зависит от $1$ и $2$: позже заканчивается $1$ (на $8$ мс), значит $3$ завершится на $8+5=13$ мс. Процесс $6$ зависит от $3$ и завершится на $13+2=15$ мс. Процесс $5$ зависит от $3$ и $4$, позже заканчивается $3$, поэтому $5$ завершится на $13+9=22$ мс.

От процесса $5$ зависят два процесса: $7$ заканчивается на $22+3=25$ мс, а $8$ — на $22+4=26$ мс. Процесс $10$ зависит от $7$ и завершится на $25+8=33$ мс, процесс $9$ зависит от $8$ и завершится на $26+10=36$ мс.

Процесс $11$ зависит от $6$ и $7$: позже заканчивается $7$ (на $25$ мс), значит $11$ завершится на $25+6=31$ мс. От него зависят сразу три процесса: $13$ заканчивается на $31+3=34$ мс, $12$ — на $31+5=36$ мс, $14$ — на $31+7=38$ мс.

Дальше два финальных процесса. Процесс $16$ зависит от $10$ и $9$, позже заканчивается $9$ (на $36$ мс), поэтому $16$ завершится на $36+10=46$ мс. Процесс $15$ зависит от $12$, $13$ и $14$: позже всех заканчивается $14$ (на $38$ мс), значит $15$ завершится на $38+9=47$ мс.

Таким образом, вся совокупность процессов завершится на $47$ мс.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-17.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]).replace(' ', '').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(max(finish(p) for p in t))   # 47

Обратите внимание, что последним завершается не тот процесс, который стоит в таблице последним по номеру. Процесс $16$ заканчивается на $46$ мс, а критический путь идёт через $15$ и упирается в $47$ мс — поэтому и нужен максимум по всем процессам, а не по последней строке.

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $1$, $2$, $4$ и $12$ завершатся на $18$, $19$, $21$ и $29$ мс соответственно.

Процесс $5$ зависит от $2$, значит завершится на $19+22=41$ мс. Процесс $8$ зависит от $1$ и завершится на $18+25=43$ мс. Процесс $3$ зависит от $1$ и $12$: позже заканчивается $12$ (на $29$ мс), поэтому $3$ завершится на $29+20=49$ мс. Процесс $7$ зависит от $5$ и завершится на $41+24=65$ мс.

Процесс $9$ зависит от $3$ и $4$, позже заканчивается $3$, значит $9$ завершится на $49+26=75$ мс. Процесс $10$ зависит от $7$ и завершится на $65+27=92$ мс. От процесса $9$ зависят $11$ (на $75+28=103$ мс) и $15$ (на $75+32=107$ мс).

Процесс $13$ зависит от $10$ и $12$: позже заканчивается $10$ (на $92$ мс), поэтому $13$ завершится на $92+30=122$ мс. Процесс $14$ зависит от $11$ и $15$, позже заканчивается $15$, значит $14$ завершится на $107+31=138$ мс. Процесс $16$ зависит от $13$ и завершится на $122+33=155$ мс.

Наконец, процесс $17$ зависит от $14$ и $16$: позже заканчивается $16$ (на $155$ мс), поэтому $17$ завершится на $155+34=189$ мс. Для сравнения, процесс $6$ зависит от $5$, $7$, $8$ и $15$ и заканчивается на $107+23=130$ мс — заметно раньше.

Таким образом, вся совокупность процессов завершится на $189$ мс.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-18.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]).replace(' ', '').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(max(finish(p) for p in t))   # 189

Процесс не может стартовать раньше, чем закончатся все, от которых он зависит, но и ждать дольше незачем — значит время его завершения равно собственной длительности плюс максимум по временам завершения предшественников. Ответ — максимум по всем процессам, потому что вся совокупность закончится тогда, когда закончится самый поздний из них.

Условие «время окончания работы всех процессов минимально» означает, что каждый процесс стартует в самое раннее допустимое время — сразу после окончания последнего из тех, от которых он зависит. Расписываем отрезки: процесс, заканчивающийся на мс $f$ и длящийся $d$ мс, занят миллисекундами с $f-d+1$ по $f$.

Независимые процессы $101$, $102$ и $109$ занимают мс $1$–$15$, $1$–$14$ и $1$–$8$. Процессы $110$ и $111$ зависят от $109$ и стартуют после $8$ мс: $110$ занимает мс $9$–$22$, $111$ — мс $9$–$14$. Процесс $113$ зависит от $111$ и занимает мс $15$–$22$. Процесс $103$ зависит от $101$ и $102$, позже заканчивается $101$ (на $15$ мс), значит $103$ занимает мс $16$–$18$. От него зависят $104$ (мс $19$–$21$) и $105$ (мс $19$–$33$), а от $104$ — процесс $106$ (мс $22$–$32$). Процесс $112$ зависит от $110$ и $111$ и занимает мс $23$–$35$, процесс $107$ — мс $34$, процесс $108$ — мс $35$–$36$.

Теперь считаем, сколько процессов идёт одновременно на каждой миллисекунде. Максимум равен $4$, и достигается он дважды. С $9$ по $14$ мс работают $101$, $102$, $110$ и $111$ — отрезок длиной $6$ мс; на $15$-й мс процессы $102$ и $111$ закончились, а добавился только $113$, и остаётся три. Второй раз четвёрка набирается с $19$ по $22$ мс: сначала это $104$, $105$, $110$ и $113$, а на $22$-й мс вместо $104$ подключается $106$. Это отрезок длиной $4$ мс, на $23$-й мс процессы $110$ и $113$ заканчиваются, а добавляется только $112$.

Самый длинный отрезок — с $9$ по $14$ мс, его продолжительность $6$ мс.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-19.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]).replace(' ', '').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)

T = max(finish(p) for p in t)
cnt = [0] * (T + 2)                   # сколько процессов идёт на каждой мс
for p in t:
    for ms in range(finish(p) - t[p] + 1, finish(p) + 1):
        cnt[ms] += 1

M = max(cnt[1:T+1])                   # максимум одновременных процессов

best = cur = 0                        # самая длинная цепочка мс со значением M
for ms in range(1, T + 1):
    cur = cur + 1 if cnt[ms] == M else 0
    best = max(best, cur)

print(best)   # 6

Спрашивается не про конкретный набор процессов, а про количество: во втором отрезке состав четвёрки на $22$-й мс меняется, но параллельных всё равно четыре. Вся совокупность процессов завершается на $36$ мс.

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $2$, $4$, $1$ и $15$ завершатся на $20$, $22$, $24$ и $24$ мс соответственно.

Процесс $5$ зависит от $2$, значит завершится на $20+25=45$ мс. Процесс $11$ зависит от $15$ и завершится на $24+22=46$ мс. Процесс $7$ зависит от $5$ и завершится на $45+18=63$ мс, процесс $8$ зависит от $1$ и $5$ (позже заканчивается $5$) и завершится на $45+22=67$ мс.

Процесс $10$ зависит от $7$ и завершится на $63+19=82$ мс. Процесс $3$ зависит от $10$ и завершится на $82+19=101$ мс. Процесс $9$ зависит от $3$ и $4$: позже заканчивается $3$, значит $9$ завершится на $101+21=122$ мс. Процесс $12$ зависит от $9$ и завершится на $122+24=146$ мс.

Процесс $13$ зависит от $10$ и $12$: позже заканчивается $12$ (на $146$ мс), поэтому $13$ завершится на $146+25=171$ мс. Процесс $16$ зависит от $13$ и завершится на $171+25=196$ мс.

Наконец, процесс $17$ зависит от $14$ и $16$: процесс $14$ закончился давно, ещё на $66$ мс, а $16$ — на $196$ мс, значит $17$ завершится на $196+22=218$ мс. Для сравнения, процесс $6$ зависит от $4$, $5$, $7$ и $8$ и заканчивается на $67+23=90$ мс — намного раньше.

Таким образом, вся совокупность процессов завершится на $218$ мс.

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-20.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]).replace(' ', '').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(max(finish(p) for p in t))   # 218

Критический путь здесь длинный: $2 \to 5 \to 7 \to 10 \to 3 \to 9 \to 12 \to 13 \to 16 \to 17$. Именно эта цепочка из десяти последовательных процессов и определяет ответ, тогда как остальные ветки заканчиваются вдвое раньше.