문제
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
각 그룹은 남은 방이 충분한 가장 이른 호텔로 가야 하므로, capacity 기준 빠른 prefix 검색이 필요합니다.
힌트 2
각 호텔의 현재 방 수를 저장하고, 임계값을 만족하는 첫 인덱스를 찾은 뒤 갱신할 수 있는 구조를 쓰세요.
힌트 3
어떤 호텔도 그룹을 수용 못 하면 0을 출력하고, 방 수는 변경하지 마세요.
예상 복잡도
시간 O((hotels + groups) log hotels), 추가 공간 O(hotels)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.