практикапошаговые заданияобработка файлабез регистрации

Практикум: строим события

Разберём метод событий изнутри: в цикле по процессам создадим события (начало +1, окончание −1), отсортируем их и пройдём со счётчиком — его максимум и есть ответ.

События

Каждый процесс даёт два события: (начало, +1) и (окончание, −1). Сложив изменения по времени, получаем число активных процессов в каждый момент.

Сортировка и счётчик

События сортируют по времени; при равном времени окончание (−1) идёт раньше начала (+1). Идя по событиям со счётчиком cur, запоминают максимум — это и есть ответ.

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

Мини-разбор: как из процессов получаются события

Слева — файл процессов, справа — список событий, который строит программа. Идите по шагам: сначала события создаются в цикле по процессам, затем сортируются, и счётчик проходит по ним по возрастанию времени. Активный шаг подсвечивает нужное.

1Создаём события

Каждый процесс даёт два события: начало (время, +1) и окончание (время, −1). Создадим их в цикле — по одному процессу за шаг.

2Процесс 1: [1, 5)

Добавляем два события: (1, +1) — начало и (5, −1) — окончание.

3Процесс 2: [2, 4)

Добавляем два события: (2, +1) — начало и (4, −1) — окончание.

4Процесс 3: [3, 6)

Добавляем два события: (3, +1) — начало и (6, −1) — окончание.

5Процесс 4: [5, 7)

Добавляем два события: (5, +1) — начало и (7, −1) — окончание.

6Процесс 5: [6, 8)

Добавляем два события: (6, +1) — начало и (8, −1) — окончание.

7Сортируем события

Теперь упорядочим события по времени. При равном времени окончание (−1) идёт раньше начала (+1) — тогда касающиеся интервалы не считаются одновременными.

8Событие 1: (1, +1)