3 Что надо знать для решения
Что надо знать для решения
Модель: начало и конец процесса
Для каждого процесса считаем две величины:
Начало (в мс от старта):
начало = МАКС(концы всех процессов, от которых он зависит). Если процесс независимый (в таблице стоит 0) — начало равно 0.Конец:
конец = начало + время выполнения.
Всё решение крутится вокруг этих двух формул. Посчитал концы всех процессов — считай, задание решено, дальше только выбираешь нужную величину под вопрос.
Про нумерацию миллисекунд
Нумерация мс начинается с 1. Процесс с началом s и временем d занимает миллисекунды с (s+1)-й по (s+d)-ю, а его «конец» равен s + d.
Например, процесс с началом 7 и временем 2 «начинается на 8-й мс, заканчивается на 9-й мс», а конец = 9. Это важно для вопросов «сколько процессов идёт на T-й мс» и «кто стартует не ранее T-й мс».
Типы вопросов
Все вопросы сводятся к концам/началам процессов:
Минимальное время всей совокупности = наибольший из концов всех процессов (самая длинная цепочка зависимостей).
Сколько процессов завершится за первые T мс = сколько процессов, у которых конец ≤ T.
Сколько процессов стартует не ранее T-й мс = сколько процессов, у которых номер мс начала ≥ T (то есть
начало + 1 ≥ T).Сколько процессов идёт параллельно на T-й мс = сколько процессов, для которых
начало < T ≤ конец.Максимальная длина отрезка с N одновременными процессами = строим «ленту времени» (кто в какую мс работает), считаем по каждой мс число работающих и ищем самый длинный участок, где их не меньше N.