Тренировки по алгоритмам от Яндекса. Лекция 7: «Сортировка событий»

YOUTUBE · 16.11.2025 08:22

Ключевые темы и таймкоды

Введение в сортировку событий

0:00

Обсуждение метода сортировки событий для решения широкого класса задач.
Примеры задач: анализ активности на сайте, исторические события, очистка дороги от снега.
Важность определения порядка событий для точного решения.

Определение событий и их порядок

2:00

События могут быть представлены как отрезки на оси времени или другой оси.
Необходимость чёткого определения порядка событий для корректного анализа.
Пример с сайтом: определение, какое событие происходит раньше — вход или выход посетителя.

Задача про сайт

3:52

Для каждого посетителя известно время входа и выхода.
Задача: определить максимальное количество людей на сайте одновременно.
Каждый посетитель порождает два события: вход и выход.

Представление и сортировка событий

5:07

События представляются парами: время и тип события.
Сортировка событий по времени и типу.
Подбор типа события для корректного порядка: сначала приход нового посетителя, затем уход старого.

Реализация алгоритма

7:44

Создание пустого списка событий.
Добавление событий для каждого посетителя: вход и выход.
Сортировка списка событий по времени и типу.
Моделирование процесса: увеличение счётчика при входе и уменьшение при выходе.

Оптимизация кода

11:44

Рекомендации по использованию констант вместо переменных для типов событий.
Избегание использования «else» для новых типов событий.
Подчёркивание важности понятного кода для промышленного проекта.

Следующая задача

12:44

Новая задача: определить суммарное время, когда на сайте был хотя бы один человек.
Применение аналогичного алгоритма для решения этой задачи.

Анализ счётчика онлайн-пользователей

13:14

Счётчик показывает количество людей онлайн.
События сортируются, и анализируется состояние счётчика.
Если счётчик положительный, добавляется время между текущим и предыдущим событием.

Обработка событий с положительным счётчиком

14:14

Если счётчик положительный, к ответу добавляется разница между текущим и предыдущим событием.
При одновременном событии счётчик увеличивается на ноль.
Если счётчик нулевой, ничего не добавляется к ответу.

Реализация алгоритма

16:06

События сортируются, счётчик онлайн равен нулю.
Цикл проходит по индексам событий, а не по самим событиям.
Если счётчик больше нуля перед текущим событием, добавляется время между текущим и предыдущим событием.

Добавление событий начальника

18:06

Начальник заходит на сайт и смотрит на счётчик онлайн.
Каждое посещение начальника фиксируется как новое событие.
События обрабатываются в порядке возрастания времени.

Обработка одновременных событий

19:51

Если несколько событий происходят одновременно, они обрабатываются в порядке их поступления.
Событие прихода начальника обрабатывается после прихода нового посетителя и до ухода старого.
Код события прихода начальника — ноль.

Оптимизация алгоритма

23:43

Можно заранее создать массив для хранения значений, увиденных начальником.
Общая сложность алгоритма зависит от количества событий.
Сортировка занимает O(n * log n).

Асимптотическая сложность

25:43

Асимптотическая сложность определяется максимальным из n и m.
Меньшее из этих чисел можно исключить из анализа.

Представление суток в виде круга

26:28

Сутки можно представить как круг, а не как прямую линию.
Пример с кассами на вокзале: дневная касса работает с 9 утра до 8 вечера, ночная — с 9 вечера до 10 утра.
Необходимо обрабатывать события, переходящие через полночь.

Разрезание событий в полночь

27:28

События разрезаются на два в момент полуночи.
Важно аккуратно разрезать события, чтобы избежать одновременного открытия кассы.
Расстояние между событиями должно быть равно нулю.

Альтернативные подходы

28:28

Введение нового типа события «касса закрылась в полночь».
Использование двух полночей: одна слева, другая справа.
Расстояние между полными должно быть равно нулю для корректного расчёта.

Второй подход — два прохода

29:28

Сортировка событий по времени в пределах суток.
Игнорирование закрытия неоткрытых касс на первом проходе.
Начало второго прохода с состояния, достигнутого на первом проходе.

Проблемы дублирования событий

33:04

Дублирование событий не решает проблему одновременного открытия и закрытия касс.
Два рассмотренных метода предпочтительнее дублирования.

Пересечение отрезков на круге

34:04

На круге пересечение двух отрезков может дать два отрезка, а не один.
Пересечение трёх отрезков даёт три отрезка и так далее.
Пример с сотрудниками: два отрезка дают два отрезка для совещания, три отрезка — три отрезка.

Задача с парковкой

36:04

Пример с парковкой в торговом центре: места в один ряд.
Без двух проходов решение задачи может быть сложным.

Введение в задачу

36:49

Парковка вдоль дороги с номерами мест.
Некоторые машины занимают несколько мест, например, длинные автомобили с прицепами.
Задача: определить, была ли парковка полностью занята в течение дня.

Анализ событий на парковке

37:49

События на парковке: прибытие и отъезд машин.
Пример: синяя машина уехала, зелёная приехала, парковка формально не была полностью занята.
Важно учитывать моменты, когда все места заняты.

Определение момента полной занятости

38:41

Необходимо определить, был ли момент, когда все места на парковке были заняты.
Отъезд машины может быть сразу заменён прибытием другой.
Используется счётчик для учёта занятых мест.

Реализация алгоритма

40:41

Машины описываются временем приезда, отъезда и занятыми местами.
Создаётся список событий: прибытие и отъезд машины.
События сортируются по количеству занятых мест.

Обработка событий

41:41

Счётчик количества занятых мест обновляется при каждом событии.
Если машина уехала, из счётчика вычитается количество занятых мест.
Если машина приехала, к счётчику прибавляется количество занятых мест.
Если счётчик равен общему количеству мест, парковка была полностью занята.

Альтернативные подходы

42:41

Можно идти по событиям напрямую, а не по индексам.
Вместо количества занятых мест можно хранить количество свободных мест.
Усложнение задачи: определить минимальное количество автомобилей, занятых на парковке.

Введение в задачу

43:26

Определение минимального количества автомобилей, занимавших парковку полностью.
Добавление счётчика для количества машин, занимающих парковочные места.
Обновление счётчиков при прибытии и отъезде машин.

Принцип работы счётчиков

44:26

При прибытии машины счётчик количества мест увеличивается на длину машины.
При отъезде машины счётчик количества машин уменьшается на единицу.
Если парковка занята полностью, минимальное количество машин выбирается из текущего и предыдущего состояний.

Усложнение задачи

45:26

Необходимость определения номеров машин, занимавших парковку полностью.
Использование множества или булевого списка для хранения номеров машин.
Возврат пустого списка, если парковка никогда не была занята полностью.

Обработка событий

46:18

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

Анализ сложности решения

50:18

Проблема частого обновления ответа при частых изменениях на парковке.
Квадратичная сложность из-за частых копий множества.
Предложение решения с двумя проходами для снижения сложности.

Двухпроходный алгоритм

53:17

Первый проход: подсчёт минимального количества машин без поддержки множества.
Второй проход: поддержка множества и возврат текущего состояния при полной занятости парковки.
Решение с временной сложностью O(m log m).

Заключение и домашнее задание

55:10

Предупреждение о сложности домашнего задания.
Упоминание о задачах, похожих на задачу про парковку, но в более сложной формулировке.
Переход к вопросам аудитории.

Обработка начальника в задаче 3

56:55

Начальник считается необычным посетителем сайта и требует особой обработки.
В боте ответы выдаются с кулдауном, чтобы не заставлять пользователя ждать.
Для задачи с кассами требуется два прохода: один для проверки закрытия неоткрытых касс, другой — для открытия новых.

Проблема одного прохода в задаче с кассами

57:55

При одном проходе невозможно правильно определить количество открытых касс одновременно.
Пример с двумя кассами показывает, что за один проход можно получить неправильный ответ.
Необходимо либо разрезать отрезки времени, либо делать два прохода.

Ошибка в задаче 6

58:55

В задаче требуется отсортировать номера машин, но не нужно сортировать их при каждом обновлении переменной.
Сортировка в конце, когда уже найден окончательный ответ, более эффективна.
Проблема может быть в условии задачи, а не в решении.

Рекомендации по решению задач

1:01:17

Для эффективного решения задач нужно внимательно читать условия, придумывать тесты и проверять решение на тестовых условиях.
Важно оценивать сложность решения и подставлять значения из условия задачи.
Если решение не проходит тесты, нужно искать ошибку и исправлять её.

Стратегия решения сложных задач

1:02:17

Если задача сложная, лучше пропустить её и перейти к следующей.
Не стоит долго зацикливаться на одной задаче, чтобы не потерять мотивацию.
Сложные задачи могут встретиться на собеседовании, но чаще всего они связаны с алгоритмическими позициями.

Заключение

1:03:17

Не стоит расстраиваться из-за неудачных попыток решить сложные задачи.
Продолжайте решать задачи, которые решаются, и возвращайтесь к сложным позже.
Вопросы можно задавать в чате.