Поиск максимального количества одновременно находящихся в отеле гостей

Условие

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

Пример входных данных: {0, 11}, {0, 2}, {1, 3}

{0, 11}:

• заезд в день 0
• выезд в день 11

Ответ программы – максимальное количество одновременно проживающих гостей.

Ответ

Используйте события заезда +1 и выезда −1, отсортированные по дате. При совпадении дат сначала обрабатывайте выезд, если день выезда уже не считается проживанием.

Для полуоткрытых интервалов [заезд, выезд) решение:

int maxGuests(const std::vector<std::pair<int, int>>& stays) {
    std::vector<std::pair<int, int>> events;
    for (auto [arrival, departure] : stays) {
        if (arrival >= departure) continue;
        events.emplace_back(arrival, 1);
        events.emplace_back(departure, -1);
    }
    std::sort(events.begin(), events.end());
    int current = 0, best = 0;
    for (auto [day, delta] : events) {
        current += delta;
        best = std::max(best, current);
    }
    return best;
}

Пример даёт 3. Время O(n log n), память O(n). Здесь пустые или обратные интервалы пропускаются; в прикладном коде обратные даты лучше отклонять при валидации. Если день выезда включён, порядок событий меняется.