1096. Hotel Room Blocks

Hard7.5 points estimatedSegment TreeDesign3 hints
RPby Rohit Parihar

A conference hotel has n rooms in one corridor, numbered 0 to n - 1, all empty at the start. Groups arrive and need rooms that sit next to each other. Design HotelBlocks to hand out such blocks.

  • checkIn(k) looks for k consecutive empty rooms. Among all possible blocks it picks the one with the smallest starting room number, marks those rooms occupied, and returns that starting number. If no block of k consecutive empty rooms exists, it returns -1 and changes nothing.
  • checkOut(start, k) makes rooms start to start + k - 1 empty. Some of them may already be empty (for example when a group leaves early in pieces); those simply stay empty.

Scanning the corridor room by room on every request is too slow for a large hotel.

Example 1

Input:
operations = ["HotelBlocks","checkIn","checkIn","checkOut","checkIn","checkIn","checkIn"]arguments = [[10],[4],[3],[2,4],[5],[4],[3]]
Output:
[null,0,4,null,-1,2,7]
Explanation:

Rooms 0-3 and 4-6 are taken; freeing 2-5 leaves runs 2-5 and 7-9, so a block of 5 does not exist (-1), a block of 4 starts at 2, and a block of 3 then starts at 7.

Example 2

Input:
operations = ["HotelBlocks","checkIn","checkIn","checkOut","checkIn"]arguments = [[1],[1],[1],[0,1],[1]]
Output:
[null,0,-1,null,0]
Explanation:

With a single room, the second check-in fails and returns -1 without changing anything; after check-out the room can be taken again.

Constraints

1 ≤ n ≤ 105

1 ≤ k ≤ n for checkIn; 0 ≤ start and start + k ≤ n for checkOut

At most 105 operations

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(log n) per operation
Space
O(n)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.