Problem
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.
Einschränkungen
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.
Beispiele
Eingabe:
rooms = [3, 1, 4]
groups = [2, 3, 2]
Erwartete Ausgabe:
expected = [1, 3, 0]Eingabe:
std::vector<long long> rooms = {3, 1, 4};
std::vector<long long> groups = {2, 3, 2};
Erwartete Ausgabe:
std::vector<long long> expected = {1, 3, 0};Eingabe:
long[] rooms = new long[] {3, 1, 4};
long[] groups = new long[] {2, 3, 2};
Erwartete Ausgabe:
long[] expected = new long[] {1, 3, 0};Erläuterung
The first group leaves [1, 1, 4]. The second uses hotel 3, leaving [1, 1, 1]. The last group of 2 cannot fit.
Eingabe:
rooms = [2, 2]
groups = [2, 2]
Erwartete Ausgabe:
expected = [1, 2]Eingabe:
std::vector<long long> rooms = {2, 2};
std::vector<long long> groups = {2, 2};
Erwartete Ausgabe:
std::vector<long long> expected = {1, 2};Eingabe:
long[] rooms = new long[] {2, 2};
long[] groups = new long[] {2, 2};
Erwartete Ausgabe:
long[] expected = new long[] {1, 2};Erläuterung
Both hotels fit the first group, so choose the earlier hotel 1. It becomes full, so the next group uses hotel 2.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Jede Gruppe muss ins erste Hotel mit genug freien Zimmern, also brauchst du schnelles Präfix-Suchen nach Kapazität.
Hinweis 2
Verfolge die aktuelle Zimmerzahl jedes Hotels in einer Struktur, die den ersten Index mit Schwellenwert findet und dann aktualisiert.
Hinweis 3
Wenn kein Hotel die Gruppe aufnehmen kann, gib 0 aus und ändere keine Zimmerzahlen.
Erwartete Komplexität
Zeit O((hotels + groups) log hotels), zusätzlicher Speicher O(hotels)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.