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

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

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

В файле содержится информация о совокупности $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$

Определите минимальное время (в мс), за которое завершатся $22$ процесса. Считать, что каждый процесс начинается в самое раннее допустимое время. Минимальное время отсчитывается непрерывно с первой миллисекунды. В ответе укажите только число – количество мс.

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

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

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

Приведём другое решение на языке 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$ — это и есть момент, когда завершится двадцать второй процесс.

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

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