1380. Slot Reserver

Medium3.5 points estimatedOrdered SetDesignIntervals
RPby Rohit Parihar

A rehearsal room is booked in back-to-back slots on a timeline that starts at 0. Design the class SlotReserver with an empty constructor and two methods.

reserve(duration) finds the earliest start time t >= 0 such that the half-open slot [t, t + duration) shares no time with any current reservation, records that reservation, and returns t. Slots that only touch at an endpoint do not conflict, and gaps left by released reservations may be reused.

release(start) removes the reservation that begins exactly at start and returns true; if no reservation begins there it changes nothing and returns false.

Keep the reservations in an ordered map from start to end and scan the gaps in order, so each call costs O(n) at worst with n at most 2000 reservations alive.

Example 1

Input:
operations = ["SlotReserver","reserve","reserve","reserve","release","reserve","reserve","release"]arguments = [[],[3],[2],[4],[3],[1],[3],[99]]
Output:
[null,0,3,5,true,3,9,false]
Explanation:

Slots land at 0, 3 and 5; releasing the one at 3 frees [3,5), so a length-1 slot takes 3, a length-3 slot does not fit in the remaining gap [4,5) and goes to 9; releasing 99 fails.

Example 2

Input:
operations = ["SlotReserver","release"]arguments = [[],[0]]
Output:
[null,false]
Explanation:

Nothing is reserved, so releasing fails.

Example 3

Input:
operations = ["SlotReserver","reserve","reserve","release","reserve","reserve"]arguments = [[],[1000000],[1000000],[0],[999999],[2]]
Output:
[null,0,1000000,true,0,2000000]
Explanation:

After the first slot is released, a slot of 999999 fits at 0 and a slot of 2 does not fit in the 1-unit gap after it, so it goes to 2000000.

Constraints

1 ≤ number of calls ≤ 2000

1 ≤ duration ≤ 106

0 ≤ start ≤ 109

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(n) per call
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.