Тренажёр: быстрый ответ
В таблице — процессы с временем начала и окончания. Процесс идёт от начала включительно до окончания не включая. Найдите, сколько процессов выполнялось одновременно в самый нагруженный момент.
Что дано
У каждого процесса известно время начала и время окончания. Процесс выполняется на промежутке [начало, окончание): в момент начала он уже работает, в момент окончания — уже нет.
Способ 1: перебор по моментам времени
Находим самое раннее начало и самое позднее окончание, затем идём по времени t по единице. Для каждого момента считаем процессы с условием начало ≤ t < окончание; максимум счётчика — ответ. Простой и наглядный способ без сортировки.
Способ 2: метод событий
Каждый процесс даёт два события: +1 в момент начала и −1 в момент окончания. Отсортируем события по времени и будем складывать изменения — получится число активных процессов в каждый момент. Максимум этого счётчика — ответ. Это быстрее перебора.
Одинаковое время
Если один процесс завершается ровно там, где начинается другой, одновременно они не работают. Поэтому при равном времени окончание (−1) обрабатывают раньше начала (+1).
Зачем программа
На экзамене процессов много, вручную не перебрать. Пишут короткую программу: прочитать пары, собрать события, отсортировать и найти максимум счётчика. В тренажёре процессов немного — можно посчитать и вручную, но метод тот же.
Как пользоваться этим режимом. Посмотрите таблицу процессов, посчитайте максимум одновременно выполнявшихся и введите число. «Проверить» сверит ответ, «Показать решение» разберёт оба способа.