Все задачи
Сложно Решена: 1 Процент решений: 100.0%

Hotel Room Allocation

Assign arriving groups in order.

Чему вы научитесь

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

Условие

Assign arriving groups in order. A group must stay entirely in the earliest hotel with enough free rooms. Subtract the group size from that hotel’s free rooms. If no hotel fits, return 0 for that group and leave all capacities unchanged. Hotel positions start at 1.

Implement hotel_room_allocation(rooms, groups).

Input

rooms: Initial free rooms per hotel, in priority order.

groups: Group sizes in arrival order.

Output

Return the selected hotel position for each group, or 0 when it cannot be placed.

Ограничения

1…200,000 hotels and 0…200,000 groups. Initial room counts are 0…1,000,000,000. Group sizes are 1…1,000,000,000. Empty groups input returns an empty list.

Примеры

Пример 1
Ввод:
rooms = [3, 1, 4]
groups = [2, 3, 2]

Ожидаемый вывод:
expected = [1, 3, 0]
Ввод:
std::vector<long long> rooms = {3, 1, 4};
std::vector<long long> groups = {2, 3, 2};

Ожидаемый вывод:
std::vector<long long> expected = {1, 3, 0};
Ввод:
long[] rooms = new long[] {3, 1, 4};
long[] groups = new long[] {2, 3, 2};

Ожидаемый вывод:
long[] expected = new long[] {1, 3, 0};

Пояснение

The first group leaves [1, 1, 4]. The second uses hotel 3, leaving [1, 1, 1]. The last group of 2 cannot fit.

Пример 2
Ввод:
rooms = [2, 2]
groups = [2, 2]

Ожидаемый вывод:
expected = [1, 2]
Ввод:
std::vector<long long> rooms = {2, 2};
std::vector<long long> groups = {2, 2};

Ожидаемый вывод:
std::vector<long long> expected = {1, 2};
Ввод:
long[] rooms = new long[] {2, 2};
long[] groups = new long[] {2, 2};

Ожидаемый вывод:
long[] expected = new long[] {1, 2};

Пояснение

Both hotels fit the first group, so choose the earlier hotel 1. It becomes full, so the next group uses hotel 2.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Каждую группу нужно отправить в самый ранний hotel с достаточным числом свободных rooms, так что нужен быстрый prefix search по capacity.

Подсказка 2

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

Подсказка 3

Если ни один hotel не подходит группе, выведи 0 и не меняй counts комнат.

Ожидаемая сложность

время O((hotels + groups) log hotels), доп. память O(hotels)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

# Участник Язык Время Память Оценка ИИ Решение
1 ННикита Python 1,009 ms - 5/5 Посмотреть код

Учитесь у других

Решения сообщества

Внимание, спойлер: ниже 1 полное решение Попробуйте сначала решить сами. Вы всегда можете посмотреть код других и AI-обзоры. Войдите и решите задание, чтобы присоединиться к обсуждению.