UniLecs #Task. Онлайн-конференция
Задача: на очередной онлайн-конференции присутствовало онлайн N участников. Но некоторые из них подключались к трансляции после его начала, а отключались — до его завершения, то есть не все из этих участников одновременно были онлайн.
Для каждого участника определите, какое количество других участников одновременно с ним было онлайн в какой-либо момент времени.
Входные данные: List(Si, Ti) — список из N элементов (Si, Ti), где Si — время подключения i-го участника к трансляции, Ti — время отключения i-го участника от трансляции.
Вывод: список из N целых чисел, где i-ое число равно кол-ву участников, которые были одновременно онлайн (в какой либо момент времени) во время конференции с i-м из участников.
Примечание: если в какой-то момент времени один участник подключается, а другой одновременно отключается, то считается, что они в этот момент одновременно находятся онлайн.
Пример:
List = {(1, 10), (2, 5), (5, 6), (1, 4)}
Output: 3, 3, 2, 2
Пояснение к примеру: 1й участник (1, 10) застал на конференции 3х участников, 2й участник (2, 5) также застал 3х участников, 3й участник (5, 6) — двоих, 4й участник (1, 4) — тоже только 2х.
Разбор
Если формализовать задачу к задаче на плоскости, то получим следующее: на прямой дано N отрезков, для каждого отрезка нужно подсчитать количество других отрезков, с которыми он пересекается.
При этом для каждого отрезка проще посчитать не количество отрезков, с которым он пересекается, а количество отрезков, с которыми он не пересекается.
Создадим список событий, добавив в него информацию обо всех концах и началах отрезков. Каждое событие хранится в виде тройки значений — номер участника, минута подключения или отключения и тип события (Подключение к конференции / Отключение от конференции), к которому относится событие.
Перед началом обработки необходимо отсортировать список по времени подключения / отключения. Для событий, у которых минута подключения / отключения одинакова, необходимо обрабатывать сначала события с подключением к конференции.
Для подсчета кол-ва подключений к конефернции и отключения от нее заведем два глобальных счетчика.
Реализация
https://gist.github.com/unilecs/dda5d2936481f1a0b7f7ee4025be6e76
