Problema
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.
Restricciones
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.
Ejemplos
Entrada:
rooms = [3, 1, 4]
groups = [2, 3, 2]
Salida esperada:
expected = [1, 3, 0]Entrada:
std::vector<long long> rooms = {3, 1, 4};
std::vector<long long> groups = {2, 3, 2};
Salida esperada:
std::vector<long long> expected = {1, 3, 0};Entrada:
long[] rooms = new long[] {3, 1, 4};
long[] groups = new long[] {2, 3, 2};
Salida esperada:
long[] expected = new long[] {1, 3, 0};Explicación
The first group leaves [1, 1, 4]. The second uses hotel 3, leaving [1, 1, 1]. The last group of 2 cannot fit.
Entrada:
rooms = [2, 2]
groups = [2, 2]
Salida esperada:
expected = [1, 2]Entrada:
std::vector<long long> rooms = {2, 2};
std::vector<long long> groups = {2, 2};
Salida esperada:
std::vector<long long> expected = {1, 2};Entrada:
long[] rooms = new long[] {2, 2};
long[] groups = new long[] {2, 2};
Salida esperada:
long[] expected = new long[] {1, 2};Explicación
Both hotels fit the first group, so choose the earlier hotel 1. It becomes full, so the next group uses hotel 2.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Cada grupo debe ir al primer hotel con suficientes habitaciones restantes, así que necesitas una búsqueda rápida por prefijos de capacidad.
Pista 2
Lleva el conteo actual de habitaciones de cada hotel en una estructura que encuentre el primer índice que cumpla el umbral y luego actualízalo.
Pista 3
Si ningún hotel puede alojar a un grupo, devuelve 0 y no cambies ningún conteo de habitaciones.
Complejidad esperada
tiempo O((hotels + groups) log hotels), espacio extra O(hotels)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.