Khó 1 đã giải Tỷ lệ chấp nhận 100.0%

Hotel Room Allocation

Assign arriving groups in order.

Bạn sẽ học được gì

  • Find the first position with enough capacity
  • Update and query a segment tree
  • Turn a slow scan into logarithmic steps

Đề bài

Xem bản dịch

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.

Ràng buộc

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.

Ví dụ

Ví dụ 1
Đầu vào:
rooms = [3, 1, 4]
groups = [2, 3, 2]

Kết quả mong đợi:
expected = [1, 3, 0]
Đầu vào:
std::vector<long long> rooms = {3, 1, 4};
std::vector<long long> groups = {2, 3, 2};

Kết quả mong đợi:
std::vector<long long> expected = {1, 3, 0};
Đầu vào:
long[] rooms = new long[] {3, 1, 4};
long[] groups = new long[] {2, 3, 2};

Kết quả mong đợi:
long[] expected = new long[] {1, 3, 0};

Giải thích

The first group leaves [1, 1, 4]. The second uses hotel 3, leaving [1, 1, 1]. The last group of 2 cannot fit.

Ví dụ 2
Đầu vào:
rooms = [2, 2]
groups = [2, 2]

Kết quả mong đợi:
expected = [1, 2]
Đầu vào:
std::vector<long long> rooms = {2, 2};
std::vector<long long> groups = {2, 2};

Kết quả mong đợi:
std::vector<long long> expected = {1, 2};
Đầu vào:
long[] rooms = new long[] {2, 2};
long[] groups = new long[] {2, 2};

Kết quả mong đợi:
long[] expected = new long[] {1, 2};

Giải thích

Both hotels fit the first group, so choose the earlier hotel 1. It becomes full, so the next group uses hotel 2.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Each group must go to the earliest hotel with enough remaining rooms, so you need fast prefix searching by capacity.

Gợi ý 2

Track each hotel's current room count in a structure that can find the first index meeting a threshold and then update it.

Gợi ý 3

If no hotel can fit a group, output 0 and do not change any room counts.

Độ phức tạp mong đợi

O((hotels + groups) log hotels) time, O(hotels) extra space

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 1,009 ms - 5/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.