Что спрашивают

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

Найдите число пиков и максимальное число людей. N < 10 000, времена натуральные от 1 до 1440, вход не позже выхода. Одинаковые посещения допустимы.

Приём решения

В одном и том же моменте входящий и выходящий оба присутствуют. Поэтому событие входа должно действовать в момент t, а событие выхода — только сразу после t. Кодируем порядок фаз: вход в 2 * begin, выход в 2 * end + 1.

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

Обходим метки по возрастанию и обновляем active. Если установлен новый максимум, старые пики больше не нужны: присваиваем peaks = 1. Если active снова равен текущему максимуму, а предыдущее состояние ниже него, начинается ещё один пик. Нулевое суммарное событие не разрывает пик.

В памяти O(N) событий, сортировка требует O(N log N). Перебор только целых минут неверен: он может склеить два максимума, разделённых непустым промежутком между минутами.

Разбор на примере

Ввод

5
8 9
2 4
5 5
9 10
4 6

Вывод

3 2
Разбор примера по шагам
Время / фазаПосетителейСмысл
Момент 42Первый пик
Между 4 и 51Пики разделены
Момент 52Второй пик
Сразу после 51Мгновенный посетитель ушёл
Момент 92Третий пик

В момент 4 одновременно находятся посетители [2; 4] и [4; 6]. Сразу после 4 остаётся один. В момент 5 к нему на один момент добавляется посетитель [5; 5]. Третий отдельный пик возникает в 9 при пересечении [8; 9] и [9; 10]. Во всех пиках по два человека.

Код на Python и C++

Не превращайте интервалы в [begin; end): это исключит момент выхода. Короткое посещение begin == end должно создавать состояние с этим человеком.

В C++ события хранятся в map<long long, int>: он перебирает моменты по возрастанию, отдельная сортировка не нужна.

import sys


def solve(visits):
    events = {}
    for begin, end in visits:
        events[2 * begin] = events.get(2 * begin, 0) + 1
        after = 2 * end + 1
        events[after] = events.get(after, 0) - 1
    active = maximum = peaks = 0
    for phase in sorted(events):
        previous = active
        active += events[phase]
        if active > maximum:
            maximum, peaks = active, 1
        elif active == maximum and active > 0 and previous != maximum:
            peaks += 1
    return peaks, maximum


if __name__ == '__main__':
    data = list(map(int, sys.stdin.buffer.read().split()))
    visits = list(zip(data[1::2], data[2::2]))
    print(*solve(visits))
#include <iostream>
#include <map>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<long long, int> events;
    for (int i = 0; i < n; i++) {
        long long begin, end;
        cin >> begin >> end;
        events[2 * begin] += 1;
        events[2 * end + 1] -= 1;
    }
    int active = 0, maximum = 0, peaks = 0;
    for (auto [phase, change] : events) {
        int previous = active;
        active += change;
        if (active > maximum) {
            maximum = active;
            peaks = 1;
        } else if (active == maximum && active > 0 && previous != maximum) {
            peaks += 1;
        }
    }
    cout << peaks << ' ' << maximum << endl;
}

Типичные ошибки

  • Вычесть выходящих до входящих

    На общем конце оба посетителя присутствуют. Исключение выходящего раньше проверки теряет мгновенный максимум.

  • Посчитать подряд идущие целые минуты

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

  • Не сбросить число при новом максимуме

    Пики старого меньшего уровня не являются пиками за сутки. При новом maximum счёт начинается заново.