Что спрашивают
Посетитель присутствует в магазине от входа до выхода включительно. Время непрерывно: между минутами 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
| Время / фаза | Посетителей | Смысл |
|---|---|---|
| Момент 4 | 2 | Первый пик |
| Между 4 и 5 | 1 | Пики разделены |
| Момент 5 | 2 | Второй пик |
| Сразу после 5 | 1 | Мгновенный посетитель ушёл |
| Момент 9 | 2 | Третий пик |
В момент 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))
<iostream>
<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 счёт начинается заново.