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.
Vincoli
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.
Esempi
Input:
rooms = [3, 1, 4]
groups = [2, 3, 2]
Output atteso:
expected = [1, 3, 0]Input:
std::vector<long long> rooms = {3, 1, 4};
std::vector<long long> groups = {2, 3, 2};
Output atteso:
std::vector<long long> expected = {1, 3, 0};Input:
long[] rooms = new long[] {3, 1, 4};
long[] groups = new long[] {2, 3, 2};
Output atteso:
long[] expected = new long[] {1, 3, 0};Spiegazione
The first group leaves [1, 1, 4]. The second uses hotel 3, leaving [1, 1, 1]. The last group of 2 cannot fit.
Input:
rooms = [2, 2]
groups = [2, 2]
Output atteso:
expected = [1, 2]Input:
std::vector<long long> rooms = {2, 2};
std::vector<long long> groups = {2, 2};
Output atteso:
std::vector<long long> expected = {1, 2};Input:
long[] rooms = new long[] {2, 2};
long[] groups = new long[] {2, 2};
Output atteso:
long[] expected = new long[] {1, 2};Spiegazione
Both hotels fit the first group, so choose the earlier hotel 1. It becomes full, so the next group uses hotel 2.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Ogni gruppo deve andare nel primo hotel con abbastanza camere residue, quindi serve una ricerca veloce per prefix sulla capacità.
Suggerimento 2
Tieni traccia del numero attuale di camere di ogni hotel in una struttura che trova il primo indice che soddisfa una soglia e poi lo aggiorna.
Suggerimento 3
Se nessun hotel può ospitare un gruppo, restituisci 0 e non cambiare nessun conteggio di camere.
Complessità attesa
tempo O((hotels + groups) log hotels), spazio aggiuntivo O(hotels)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.