В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что
Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы — время его выполнения в миллисекундах, в третьей строке перечислены
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Типовой пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 1 | 1;2 |
| 4 | 7 | 3 |
В данном случае независимые
Отсортируем данные в таблице так, чтобы все независимые процессы оказались в начале таблицы и любой процесс был расположен после всех процессов, от которых он зависит. Также в таблицу добавим столбец «Время окончания процесса» и запишем туда длительности независимых процессов.
| A | B | C | D |
|---|---|---|---|
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A | |
| 1 | 7 | 0 | 7 |
| 2 | 6 | 0 | 6 |
| 3 | 4 | 2 | |
| 4 | 5 | 3 | |
| 5 | 9 | 0 | 9 |
| 6 | 7 | 1;2 | |
| 7 | 6 | 5;6 | |
| 8 | 7 | 3;7 | |
| 9 | 5 | 5 | |
| 10 | 7 | 9 | |
| 11 | 9 | 6 | |
| 12 | 5 | 9 | |
| 13 | 3 | 0 | 3 |
| 14 | 8 | 12;13 | |
| 15 | 6 | 5;14 |
Далее рассчитаем время выполнения оставшихся процессов:
f(3) = 4 + f(2) = 4 + 6 = 10;
f(4) = 5 + f(3) = 5 + 10 = 15;
f(6) = 7 + max(f(1), f(2)) = 7 + 7 = 14;
f(7) = 6 + max(f(5), f(6)) = 6 + 14 = 20;
f(8) = 7 + max(f(3), f(7)) = 7 + 20 = 27;
f(9) = 5 + f(5) = 5 + 9 = 14;
f(10) = 7 + f(9) = 7 + 14 = 21;
f(11) = 9 + f(6) = 9 + 14 = 23;
f(12) = 5 + f(9) = 5 + 14 = 19;
f(14) = 8 + max(f(12), f(13)) = 8 + 19 = 27;
f(15) = 6 + max(f(5), f(14)) = 6 + 27 = 33.
| A | B | C | D |
|---|---|---|---|
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A | |
| 1 | 7 | 0 | 7 |
| 2 | 6 | 0 | 6 |
| 3 | 4 | 2 | 10 |
| 4 | 5 | 3 | 15 |
| 5 | 9 | 0 | 9 |
| 6 | 7 | 1;2 | 14 |
| 7 | 6 | 5;6 | 20 |
| 8 | 7 | 3;7 | 27 |
| 9 | 5 | 5 | 14 |
| 10 | 7 | 9 | 21 |
| 11 | 9 | 6 | 23 |
| 12 | 5 | 9 | 19 |
| 13 | 3 | 0 | 3 |
| 14 | 8 | 12;13 | 27 |
| 15 | 6 | 5;14 | 33 |
Ответ: 33.
Приведём решение на языке Python.
def f(d):
if d[2] == [0]:
return d[1]
else:
maxx = 0
for i in d[2]:
if maxx < f(index[i - 1]):
maxx = f(index[i - 1])
return maxx + d[1]
from csv import reader
with open("22_30.csv") as F:
s = reader(F, delimiter=';', quotechar='"')
next(s)
index = []
for i in s:
index.append([int(i[0]), int(i[1]), list(map(int, str(i[2]).split(';')))])
for i in range(len(index)):
print(i + 1, f(index[i]))
Примечание.
Для считывания информации из файла необходимо конвертировать его из xlsx в csv.
Приведём решение Виктории Сапроновой на языке С#.
Dictionary Dictionary foreach (var line in File.ReadAllLines(«22.csv")) { var fields = line.Split(',').Select(s => s.Trim()).ToArray(); var id = int.Parse(fields[0]); var time = int.Parse(fields[1]); List fields[2].Split(';').Select(int.Parse).ToList(); processes[id] = new Process(id, time, deps); } var result = processes.Keys.Select(EvalTime).Max(); System.Console.WriteLine(result); int EvalTime(int id) { if (times.TryGetValue(id, out var t)) return t; var p = processes[id]; var time = p.Time; if (p.Dependencies.Count > 0) time += p.Dependencies.Select(EvalTime).Max(); times[id] = time; return time; } record Process(int Id, int Time, List