Problème
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.
Contraintes
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.
Exemples
Entrée :
rooms = [3, 1, 4]
groups = [2, 3, 2]
Sortie attendue :
expected = [1, 3, 0]Entrée :
std::vector<long long> rooms = {3, 1, 4};
std::vector<long long> groups = {2, 3, 2};
Sortie attendue :
std::vector<long long> expected = {1, 3, 0};Entrée :
long[] rooms = new long[] {3, 1, 4};
long[] groups = new long[] {2, 3, 2};
Sortie attendue :
long[] expected = new long[] {1, 3, 0};Explication
The first group leaves [1, 1, 4]. The second uses hotel 3, leaving [1, 1, 1]. The last group of 2 cannot fit.
Entrée :
rooms = [2, 2]
groups = [2, 2]
Sortie attendue :
expected = [1, 2]Entrée :
std::vector<long long> rooms = {2, 2};
std::vector<long long> groups = {2, 2};
Sortie attendue :
std::vector<long long> expected = {1, 2};Entrée :
long[] rooms = new long[] {2, 2};
long[] groups = new long[] {2, 2};
Sortie attendue :
long[] expected = new long[] {1, 2};Explication
Both hotels fit the first group, so choose the earlier hotel 1. It becomes full, so the next group uses hotel 2.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Chaque groupe doit aller dans le premier hôtel ayant assez de chambres restantes, donc il faut une recherche de préfixe rapide par capacité.
Indice 2
Suivez le nombre de chambres actuel de chaque hôtel dans une structure qui peut trouver le premier index satisfaisant un seuil puis le mettre à jour.
Indice 3
Si aucun hôtel ne peut accueillir un groupe, renvoyez 0 et ne modifiez aucun nombre de chambres.
Complexité attendue
temps O((hotels + groups) log hotels), espace supplémentaire O(hotels)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.