Сортировка событий

О сортировке в C++

Научимся сортировать по особым ключам. Для этого используем лямбда-функции.

Синтаксис лямбда-функций: [captures](params) { body }

#include <iostream>

int main() {
  // Лямбда-функция, удваивающая число
  auto func = [](int x) { return 2 * x; };
  
  std::cout << func(15) << std::endl;  // 30
  std::cout << func(-3) << std::endl;  // -6
  
  return 0;
}

Такие функции можно использовать как компараторы для сортировки. Например, в следующем примере сортировка будет проводиться по убыванию:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> data = {4, 1, 5, 3, 2};
  
  // Сортировка по возрастанию (по умолчанию)
  std::sort(data.begin(), data.end());
  // data: [1, 2, 3, 4, 5]
  
  // Сортировка по убыванию с использованием лямбды
  std::sort(data.begin(), data.end(), [](int a, int b) {
    return a > b;  // Возвращаем true, если a должен идти перед b
  });
  // data: [5, 4, 3, 2, 1]
  
  return 0;
}

Пары (std::pair) и кортежи (std::tuple) по умолчанию сравниваются лексикографически, то есть как слова в орфографических словарях: сначала по первому элементу, при их равенстве по второму, при равенстве первого и второго – по третьему и так далее.
- {1, 2} < {1, 3} < {2, 2} < {2, 3}
- std::make_tuple(1, 2) < std::make_tuple(1, 2, 3) < std::make_tuple(2, 2)

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

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<std::pair<int, int>> data = {{1, 2}, {5, 1}, {3, 1}, {1, 3}};
  
  // Сортировка: сначала по второму элементу, затем по первому
  std::sort(data.begin(), data.end(), [](const auto& a, const auto& b) {
    if (a.second != b.second) {
      return a.second < b.second;  // По возрастанию второго элемента
    }
    return a.first < b.first;      // По возрастанию первого элемента
  });
  // data: [{3, 1}, {5, 1}, {1, 2}, {1, 3}]
  
  return 0;
}

Наиболее сложные сортировки: сначала по возрастанию первого элемента, затем по убыванию второго:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<std::pair<int, int>> data = {{1, 2}, {5, 1}, {3, 1}, {1, 3}};
  
  // Сортировка: по возрастанию первого, по убыванию второго
  std::sort(data.begin(), data.end(), [](const auto& a, const auto& b) {
    if (a.first != b.first) {
      return a.first < b.first;   // По возрастанию первого элемента
    }
    return a.second > b.second;   // По убыванию второго элемента
  });
  // data: [{1, 3}, {1, 2}, {3, 1}, {5, 1}]
  
  return 0;
}

Сортировка событий – метод сканирующей прямой

Сортировка событий, он же метод сканирующей прямой (sweep line) – алгоритм обработки событий оптимальным образом и нахождение некоторой информации. В каких задачах можно применить этот метод и в чем он заключается рассмотрим в этом разделе.

Посетители сайта

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

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

Формализовать это задачу можно через отрезки и точки на прямой. У нас есть \(n\) отрезков \([l_i; r_i]\). Хотим найти такую точку \(m\), которая принадлежит наибольшему кол-ву отрезков:

\(m_{max} = \max_m \sum_{i = 1}^n \Big\{ m \in [l_i; r_i] \Big\}\)

Наивный подход

Давайте перебирать все возможные моменты времени: \(m \in [\min_i l_i; \max_i r_i]\), то есть от самого раннего до самого позднего момента, когда что-то у нас происходило. И для каждого такого момента перебирать все отрезки и подсчитывать, в скольких отрезках он лежит.

Сложность такого алгоритма составит \(O\left((\max_i r_i - \min_i l_i) \cdot n \right)\), что очень неоптимально при разреженных данных: когда событий мало, а разброс времени огромный. Более того, при выборе разных единиц времени сложность будет кратно увеличиваться. Например, при переходе от минут к секундам количество операций увеличится в 60 раз. А что если нужно получить информацию с точностью до долей секунды?

Хотим изобрести алгоритм, который будет линейно зависеть от количества событий, а не от информации в них.

Более оптимальный подход

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

Пусть информация о каждом пользователе порождает 2 события:

пользователь пришел – \((t_{in}, 0)\)
пользователь ушел – \((t_{out}, 1)\)

где \(t\) – момент времени когда это произошло

Отсортируем набор таких событий лексикографически (сравниваем по первому элементу; при равенстве первых, по второму элементу). Получим что-то вроде:

\((t_1, 0), (t_2, 0), (t_2, 1), (t_3, 1), (t_4, 0), \text{ где } t_1 < t_2 < t_3 < t_4\)

Подсчитаем вручную количество пользователей в каждом из отрезков:

\((- \infty; t_1)\) – 0 пользователей
\([t_1; t_2) \cup [t_2; t_3) = [t_1; t_3)\) – 1 пользователь, потому что в момент времени \(t_2\) пользователи “бесшовно сменили” друг друга, их количество не изменилось
\([t_3; t_4)\) – 0 пользователей
\([t_4; + \infty)\) – 1 пользователь

Действительно, это достаточно легко делать на отсортированном массиве:

если встречаем событие подключения, то
- \(cnt += 1\)
- и обновляем максимум: \(max\_cnt = \max(max\_cnt, cnt)\)
если встречаем событие отключения, то
- \(cnt -= 1\)

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

Оценим сложность алгоритма:

\(n\) логов → \(2n\) событий
сортировка за \(O(n \log {n})\)
обработка событий за \(O(n)\)

Итоговая сложность: \(O(n \log n)\) и то только из-за сортировки. Обработка событий линейна и не зависит от выбора моментов времени.

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

пользователь пришел – \((t_{in}, 0)\)
начальник спрашивает статистику – \((t_{boss}, 1)\)
пользователь ушел – \((t_{out}, 2)\)

Поскольку мы используем лексикографическую сортировку, ответ на вопрос начальника произойдет, когда в один момент времени все подключились. Отключаться в этот момент времени все будут после того, как начальник получил свою статистику. Это вопрос соглашения и в разных задачах может требоваться разный приоритет. Главное, что мы можем легко его настроить с помощью рассмотренного подхода.

#include <algorithm>
#include <iostream>
#include <vector>

// Типы событий с приоритетами для лексикографической сортировки.
// Меньшее значение = более высокий приоритет при обработке.
enum EventType {
  kOpenEvent = 0,     // Пользователь подключился
  kRequestEvent = 1,  // Начальник запрашивает статистику
  kCloseEvent = 2     // Пользователь отключился
};

// Структура события: время и тип
struct Event {
  int time;
  EventType type;
  
  // Оператор сравнения для лексикографической сортировки
  bool operator<(const Event& other) const {
    if (time != other.time) {
      return time < other.time;
    }
    return type < other.type;
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int num_sessions, num_requests;
  std::cin >> num_sessions >> num_requests;
  
  std::vector<Event> events;
  events.reserve(2 * num_sessions + num_requests);
  
  // Считываем сессии пользователей
  for (int i = 0; i < num_sessions; ++i) {
    int start, stop;
    std::cin >> start >> stop;
    events.push_back({start, kOpenEvent});
    events.push_back({stop, kCloseEvent});
  }
  
  // Считываем моменты запросов начальника
  for (int i = 0; i < num_requests; ++i) {
    int point;
    std::cin >> point;
    events.push_back({point, kRequestEvent});
  }
  
  // Сортируем события
  std::sort(events.begin(), events.end());
  
  int cnt = 0;  // Текущее количество пользователей
  
  // Обрабатываем события в хронологическом порядке
  for (const auto& event : events) {
    switch (event.type) {
      case kOpenEvent:
        ++cnt;
        break;
      case kRequestEvent:
        std::cout << cnt << "\n";
        break;
      case kCloseEvent:
        --cnt;
        break;
    }
  }
  
  return 0;
}

Кассы

Пусть у нас есть \(n\) касс для продажи билетов, некоторые кассы могут быть круглосуточными. Нужно определить, в течение какого времени на вокзале работают все кассы.

Применим сортировку событий, для этого отобразим график работы касс в события открытия и закрытия. Считаем, что в \(t_{open}\) касса уже работает, а в \(t_{close}\) касса уже не работает.

\(t_{open} < t_{close}\) – касса открылась и закрылась в указанные времена – 2 события
\(t_{open} > t_{close}\) – касса открылась в указанное время, доработала до полуночи, закрылась, сразу открылась и закрылась в указанное время – 4 события
\(t_{open} = t_{close}\) – касса работает круглосуточно – 0 событий. Действительно, можно учесть в счетчике, что касса работает всегда, и вообще не добавлять события

Теперь можем пройти по событиям и накапливать количество открытых касс в счетчик. Тогда если \(cnt = n\), то все кассы открыты до ближайшего закрытия или до полуночи.

Дополнительные задачи на метод сканирующей прямой

Объединение отрезков

Задача: Дано \(n\) отрезков на прямой. Найти суммарную длину их объединения.

Идея: Каждый отрезок \([l_i, r_i]\) порождает два события: открытие в \(l_i\) и закрытие в \(r_i\). Проходя по событиям слева направо, подсчитываем “глубину покрытия” – сколько отрезков покрывают текущую точку. Когда глубина становится положительной, начинаем накапливать длину; когда глубина становится нулевой – останавливаемся.

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

Задача: Дано \(n\) отрезков и \(m\) точек. Для каждой точки определить, скольким отрезкам она принадлежит.

Идея: Объединяем точки и концы отрезков в один поток событий. Точки-запросы обрабатываются между открытиями и закрытиями отрезков в одной координате.

Советы по реализации

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