Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

22. Вычислительные процессы: Определите минимальное время (в мс), за которое завершатся 17…

Задание #298204
Решено верно
Решено неверно
Сообщить о проблеме

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

Например, для приведённой таблицы найдём время, за которое завершатся $3$ процесса. Минимальное время, которое для этого требуется, – $7$ мс. За это время завершатся процессы $1$, $2$ и $4$.

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

Время, мсID процессаВсего завершено
$2$$121$$1$
$3$$106$$2$
$4$$112$$3$
$5$$125$$4$
$6$$103$, $116$, $122$$7$
$8$$105$, $115$$9$
$9$$102$, $108$, $111$$12$
$11$$109$, $124$$14$
$12$$107$, $117$, $120$$17$
$13$$110$$18$
$15$$118$, $123$$20$
$16$$113$, $114$$22$
$17$$101$$23$
$18$$104$$24$
$21$$119$$25$

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

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение