Максимум одновременных интервалов

1. Идея

Нужно найти, в какой момент времени одновременно активно максимальное число интервалов.

Если бы значения времени были маленькими, можно было бы завести массив и для каждого интервала [l, r] делать:

• +1 в точке l
• -1 в точке r + 1

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

Но здесь координаты могут быть до 10^9, поэтому массив такого размера делать нельзя.

Значит, будем хранить только важные точки — события:

• в l число активных интервалов увеличивается на 1
• в r + 1 число активных интервалов уменьшается на 1

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

2. Наблюдения

Наблюдение 1

Интервал [l, r] включительный, то есть он покрывает все точки от l до r, включая границы.

Поэтому уменьшать количество активных интервалов нужно не в r, а в r + 1.

Например, если есть интервал [2, 5], то:

• начиная с 2 он активен;
• в точках 2, 3, 4, 5 он должен учитываться;
• начиная с 6 он уже не активен.

Значит, событие окончания — это -1 в точке 6.

Наблюдение 2

Между двумя соседними событиями количество активных интервалов не меняется.

Это значит, что проверять каждую возможную координату не нужно — достаточно рассмотреть только точки, где что-то изменилось.

Наблюдение 3

Если в одной и той же координате происходит несколько событий, их удобно сначала сложить.

Например, если в точке x:

• два интервала начинаются,
• один заканчивается,

то суммарное изменение равно +1.

Именно так и делает код: для всех событий с одинаковой координатой считается общий delta.

3. Алгоритм

1. Считать n.
2. Для каждого интервала [l, r]:
   • добавить событие (l, +1)
   • добавить событие (r + 1, -1)
3. Отсортировать все события по координате.
4. Идти по отсортированному списку:
   • собрать все события с одной и той же координатой;
   • посчитать их суммарное изменение delta;
   • прибавить delta к текущему числу активных интервалов current;
   • обновить ответ answer = max(answer, current).
5. Вывести answer.

4. Почему это работает

Рассмотрим, что означает значение current после обработки всех событий в некоторой координате x.

К этому моменту:

• мы уже учли все интервалы, которые начались в x, потому что в x добавляется +1;
• мы уже убрали все интервалы, которые закончились до x, потому что для интервала [l, r] удаление происходит в r + 1.

Значит, после применения всех изменений в точке x переменная current равна числу интервалов, содержащих точку x.

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

Следовательно:

• на каждом шаге current — это корректное число одновременно активных интервалов;
• максимум среди всех таких значений и есть ответ задачи.

Именно поэтому алгоритм работает правильно.

5. Сложность

Пусть всего 2n событий.

• Построение списка событий: O(n)
• Сортировка событий: O(n log n)
• Один проход по отсортированному списку: O(n)

Итоговая сложность: O(n log n)

Память: O(n)

6. Код на C++17

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

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<pair<long long, int>> events;
    events.reserve(2LL * n);

    for (int i = 0; i < n; i++) {
        long long l, r;
        cin >> l >> r;
        events.push_back({l, 1});
        events.push_back({r + 1, -1});
    }

    sort(events.begin(), events.end());

    long long current = 0;
    long long answer = 0;
    int m = (int)events.size();
    int i = 0;

    while (i < m) {
        long long x = events[i].first;
        long long delta = 0;

        while (i < m && events[i].first == x) {
            delta += events[i].second;
            i++;
        }

        current += delta;
        if (current > answer) {
            answer = current;
        }
    }

    cout << answer << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
events = []

for _ in range(n):
    l, r = map(int, input().split())
    events.append((l, 1))
    events.append((r + 1, -1))

events.sort()

current = 0
answer = 0
i = 0
m = len(events)

while i < m:
    x = events[i][0]
    delta = 0
    while i < m and events[i][0] == x:
        delta += events[i][1]
        i += 1
    current += delta
    if current > answer:
        answer = current

print(answer)