Tous les défis
Difficile 1 résolu 100.0 % de réussite

Hotel Room Allocation

Assign arriving groups in order.

Ce que vous allez apprendre

  • Trouver la première position avec assez de capacité
  • Mettre à jour et interroger un arbre de segments
  • Transformer un parcours lent en étapes logarithmiques

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

Exemple 1
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.

Exemple 2
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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 1,009 ms - 5/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.