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.

Что надо знать для решения — Задание 22 ЕГЭ 2027 | Методички — Профиматика