समस्या
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.
सीमाएँ
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.
उदाहरण
इनपुट:
rooms = [3, 1, 4]
groups = [2, 3, 2]
अपेक्षित आउटपुट:
expected = [1, 3, 0]इनपुट:
std::vector<long long> rooms = {3, 1, 4};
std::vector<long long> groups = {2, 3, 2};
अपेक्षित आउटपुट:
std::vector<long long> expected = {1, 3, 0};इनपुट:
long[] rooms = new long[] {3, 1, 4};
long[] groups = new long[] {2, 3, 2};
अपेक्षित आउटपुट:
long[] expected = new long[] {1, 3, 0};व्याख्या
The first group leaves [1, 1, 4]. The second uses hotel 3, leaving [1, 1, 1]. The last group of 2 cannot fit.
इनपुट:
rooms = [2, 2]
groups = [2, 2]
अपेक्षित आउटपुट:
expected = [1, 2]इनपुट:
std::vector<long long> rooms = {2, 2};
std::vector<long long> groups = {2, 2};
अपेक्षित आउटपुट:
std::vector<long long> expected = {1, 2};इनपुट:
long[] rooms = new long[] {2, 2};
long[] groups = new long[] {2, 2};
अपेक्षित आउटपुट:
long[] expected = new long[] {1, 2};व्याख्या
Both hotels fit the first group, so choose the earlier hotel 1. It becomes full, so the next group uses hotel 2.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
हर group को पर्याप्त remaining rooms वाले सबसे पहले hotel में भेजना है, इसलिए capacity पर fast prefix searching चाहिए।
संकेत 2
हर hotel का current room count ऐसी structure में track करो जो threshold पूरा करने वाला पहला index ढूँढ सके, फिर उसे update करे।
संकेत 3
अगर कोई hotel group को fit न कर सके, तो 0 output करो और room counts न बदलो।
अपेक्षित जटिलता
समय O((hotels + groups) log hotels), अतिरिक्त स्थान O(hotels)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।