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

В качестве примера, скажем, у вас есть 3 задачи.

Первое задание занимает 10 единиц времени, второе - 5 единиц времени, третье - 6 единиц времени.

Ограничение состоит в том, что 2-я задача не может быть запущена, пока не будет завершена 3-я задача.

Учитывая это, вы можете сделать вывод, что минимальное время, необходимое для выполнения всех задач при соблюдении приоритета, составляет 11.

Это потому, что вы можете выполнять задачи 1 и 3 (которые занимают время 10 и 6 соответственно) одновременно, и после того, как задача 3 будет завершена, вы можете приступить к задаче 2 (которая занимает 5 единиц времени). Таким образом, все задачи завершатся в момент времени 11.

Кажется, что это можно решить с помощью топологической сортировки, которая даст вам порядок выполнения задач для удовлетворения ограничений.

Например, в задаче, после топологической сортировки задач вы получите

Task 1 (10 Units of time) -> Task 3 (6 Units of time) -> Task 2 (5 Units of time)

Однако, как только вы получите этот порядок, в котором выполняются задачи, как вы определяете, какие из них можно выполнять одновременно, а какие нужно выполнять один за другим? Кроме того, как рассчитать минимальное время, необходимое для их завершения?