22
1 балл демоверсия ЕГЭ-2026
Многопоточные вычисления: максимальное число одновременных процессов
Задание 22 · Билет 1 · ЕГЭ по информатике
Билеты — задания в формате экзамена: открытый сборник или тренировочные по образцу. Это тренировочные материалы, а не официальные КИМ. Ответы пересчитаны и сверены.
Условие
В файле содержится информация о 400 процессах. Для каждого процесса в отдельной строке записаны два натуральных числа: время начала и время окончания. Процесс выполняется начиная с момента начала включительно и до момента окончания не включая его. Процессы выполняются параллельно.
Скачивать не обязательно: если решаете на сайте, данные уже есть в программе. Скачайте, только чтобы посмотреть файл отдельно на компьютере.
Вопрос. Определите максимальное число процессов, которые выполнялись одновременно. В ответе укажите одно целое число.
Попробуйте программой
Необязательно, но удобно: напишите здесь свой код на Python, который найдёт ответ. Если не получится — откройте решение и вставьте готовую программу одной кнопкой.
Решите программой на Python
в браузереНапишите свой код, который найдёт ответ, и нажмите «Выполнить». Горячая клавиша запуска: Ctrl/⌘ + Enter.
Файл задачи уже в песочнице: task22-1-processy.txt — читайте через open('task22-1-processy.txt').
Результат
Здесь появится вывод print().
Разбор задачи
Задание 22 ЕГЭ по информатике — многопоточные вычисления: дан файл, в котором для каждого процесса указаны время начала и время окончания. Нужно найти, сколько процессов выполнялось одновременно в самый нагруженный момент.
Процессов много, вручную не перебрать, поэтому считают короткой программой: каждый процесс превращают в два события — начало и окончание.
Что важно знать
- Задание повышенного уровня — оценивается в 1 балл
- Ответ — одно целое число: максимум одновременно выполнявшихся процессов
- Процесс идёт от начала включительно до окончания не включая
План решения
- Прочитайте файл: в каждой строке — время начала и время окончания процесса.
- Превратите каждый процесс в два события: +1 в момент начала и −1 в момент окончания.
- Отсортируйте события по времени; при равенстве окончание идёт раньше начала.
- Идите по событиям, складывая изменения, и запоминайте максимум счётчика.
- Запишите наибольшее значение счётчика.
Не знаешь, как решать?
Открыть тренажёрПотренируйся на процессах: тренажёр соберёт новый набор интервалов и попросит найти максимум одновременно выполнявшихся процессов.
Решение
Теория с нуля: что нужно знать
1. О чём задача
В задании 22 дан файл с процессами: для каждого указаны время начала и время окончания. Процессы выполняются параллельно, и нужно найти, сколько процессов работало одновременно в самый нагруженный момент. Ответ — одно число: максимум одновременно выполнявшихся процессов.
2. Как читать файл программой
В каждой строке файла два целых числа — начало и окончание процесса. Пары удобно собрать в список:
data = [tuple(map(int, line.split())) for line in open("file.txt")]
Файл задачи уже загружен в песочницу под тем же именем, что и в условии: откройте его через open(...), скачивать на компьютер не нужно.3. Способ 1: перебор по моментам времени
Найдём самое раннее начало процесса и самое позднее окончание. Затем пройдём по времени t от минимума до максимума с шагом 1 и для каждого t посчитаем процессы, охватывающие этот момент: у которых начало ≤ t < окончание. Максимум счётчика — ответ.
for t in range(lo, hi + 1):
Метод простой и наглядный, сортировка не нужна; на больших файлах он медленнее.4. Способ 2: метод событий
Каждый процесс превращают в два события: начало (+1) и окончание (−1). Если отсортировать события по времени и складывать изменения, получится число активных процессов в каждый момент.
events.sort() # при равном времени −1 идёт раньше +1
Максимум счётчика за проход — ответ. Это метод событий (sweep line): быстрее перебора — O(N·log N) вместо O((max−min)·N).5. Граница времени и ответ
Процесс занимает промежуток [начало, окончание): завершившийся в момент t уже не выполняется, а начавшийся в t — выполняется. Именно поэтому в обоих способах окончание обрабатывается строго (в переборе — t < окончание, в событиях — «окончание раньше начала»). В ответ идёт одно число — наибольшее значение счётчика.
Решение
открыто шагов: 5 из 51 Шаг 1
Способ 1 — перебор по моментам времени. Найдём самое раннее начало и самое позднее окончание; здесь это 8 и 3233. Пройдём t по единице и для каждого момента посчитаем процессы с условием «начало ≤ t < окончание». Всего 3226 моментов × 400 процессов.
2 Шаг 2
Максимум перебора достигается в момент 1235: одновременно выполняется 41 процесс. Значит, ответ способа 1 — 41.
3 Шаг 3
Способ 2 — метод событий. Каждый процесс даёт событие «начало» (+1) и «окончание» (−1). Отсортируем 800 событий по времени (при равенстве окончание раньше начала) и найдём максимум счётчика активных процессов — тот же момент и то же число 41.
4 Шаг 4
Короткие программы для обоих способов читают файл task22-1-processy.txt (он уже в песочнице). В разделе решения два кода, каждый можно вставить в песочницу кнопкой.
5 Шаг 5
Оба способа дают 41. Ответ: 41.
Способ 1 · перебор по моментам времени
data = [tuple(map(int, line.split())) for line in open('task22-1-processy.txt')] # пары (начало, окончание)
lo = min(s for s, e in data) # самое раннее начало
hi = max(e for s, e in data) # самое позднее окончание
best = 0
for t in range(lo, hi + 1): # идём по времени по единице
cur = 0
for s, e in data: # сколько процессов охватывают момент t
if s <= t < e: # начало включительно, окончание — нет
cur += 1
best = max(best, cur)
print(best) # максимальное число одновременных процессов Способ 2 · метод событий
data = [tuple(map(int, line.split())) for line in open('task22-1-processy.txt')] # пары (начало, окончание)
events = [] # события: (время, изменение)
for s, e in data:
events.append((s, 1)) # в момент начала процессов на 1 больше
events.append((e, -1)) # в момент окончания — на 1 меньше
events.sort() # при равном времени окончание (−1) раньше начала (+1)
cur = 0 # сколько процессов выполняется сейчас
best = 0 # максимум за всё время
for t, d in events:
cur += d
best = max(best, cur)
print(best) # максимальное число одновременных процессов Правильный ответ этого билета: 41
Проверка: независимый пересчёт по прилагаемому файлу даёт 41 (перебор по моментам и метод событий сходятся; см. tools/task22/verify.py).
Проверка
Типовые ошибки и проверка
- Считают процессы, у которых совпал момент окончания одного и начала другого, одновременными — а они не пересекаются.
- Берут модуль числа активных процессов или путают максимум с суммой длительностей.
- В переборе берут только моменты, когда что-то начинается, — но максимум может достигаться и «в середине» интервала; нужно идти по всем целым моментам.
- В методе событий забывают отсортировать события или не учитывают порядок «окончание раньше начала» при равном времени.
- Проверка: прогоните решение на нескольких процессах вручную, затем сверьте максимум на полном файле. Оба способа должны дать одно и то же число.
Режимы
Сейчас открыт режим обучения: теория, разбор и ответ видны. Скоро появится режим проверки — только условие и поле ответа, без подсказок.
Практикум Все задания Режим проверки — скоро
Частые вопросы
Что проверяет задание 22 ЕГЭ по информатике?
Умение обрабатывать данные о процессах: по временам начала и окончания найти максимальное число процессов, выполнявшихся одновременно.
Как учитывать процессы на границе времени?
Процесс выполняется на промежутке [начало, окончание): завершившийся в момент t уже не выполняется, а начавшийся в t — выполняется. Поэтому при равном времени окончание обрабатывают раньше начала.
Можно ли решить задание 22 без программы?
На экзамене процессов много, вручную не перебрать. Нужна короткая программа, которая считает максимум методом событий (sweep line).
Что такое метод событий?
Каждый процесс даёт событие «начало» (+1) и «окончание» (−1). События сортируют по времени и складывают изменения — получается число активных процессов в каждый момент, а его максимум и есть ответ.
Можно ли потренировать задание 22?
Да. Тренажёр «Многопоточные вычисления» генерирует новые наборы процессов и просит найти максимум одновременно выполнявшихся, а затем показывает разбор методом событий.