1798. Hotel Room Upgrades
A small hotel has rooms whose capacities are listed in roomSizes. Guests arrive in non-decreasing order of arrivals[i]; guest i stays for stays[i] time units and needs a room of size at least needs[i]. When guest i arrives at time t, every room whose current guest checks out at or before t (arrival time plus stay) becomes free first. Then the guest is given the free room of the smallest size that is at least needs[i], or is turned away if no such free room exists; a turned-away guest never returns. Guests are processed in the given order, and equal-size rooms are interchangeable. Return the number of guests turned away. Aim for O((r + g) log (r + g)) time and O(r + g) space. There are up to 10^5 rooms and 10^5 guests, with sizes and needs up to 10^9.
Example 1
- Input:
- roomSizes = [4,8,6]arrivals = [0,1,2,5]stays = [10,3,4,2]needs = [5,5,7,4]
- Output:
- 1
- Explanation:
Guest 0 takes the size-6 room, guest 1 takes size 8, guest 2 needs 7 and finds nothing free (turned away); guest 3 at time 5 gets the size-4 room, so one guest is turned away.
Example 2
- Input:
- roomSizes = [5]arrivals = [0,3,3]stays = [3,5,1]needs = [5,5,5]
- Output:
- 1
- Explanation:
The only room is taken at time 0 until time 3; at time 3 it is free again for guest 1, which blocks guest 2, so one guest is turned away.
Constraints
1 ≤ roomSizes.length ≤ 105; guests g = arrivals.length = stays.length = needs.length, 1 ≤ g ≤ 105; arrivals is non-decreasing, 0 ≤ arrivals[i] ≤ 109; 1 ≤ stays[i] ≤ 108; 1 ≤ roomSizes[i], needs[i] ≤ 109.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 6,000 msC++ 1,500 msJava 3,000 msJavaScript 3,000 msTypeScript 3,000 ms
Expected complexity
- Time
- O((r + g) log (r + g))
- Space
- O(r + g)