957. Peak Overlap Bookings

Hard7.5 points estimatedSegment TreeDesignIntervalsLine SweepOrdered Set3 hints
RPby Rohit Parihar

A concert hall accepts reservations for its stage over a very long timeline of whole-second timestamps. Implement the class PeakBookings with an empty constructor and one method, book(start, end).

Each call reserves the half-open time window from start up to but not including end; a window ending exactly when another begins does not overlap it. Every call is accepted, there are no rejections. After adding the new window, book returns the largest number of reserved windows that are active at the same instant, taken over all windows booked so far (including this one). Calls are applied in the given order; the expected output holds each returned value, with null for the constructor call.

Example 1

Input:
operations = ["PeakBookings","book","book","book","book"]arguments = [[],[10,20],[15,25],[20,30],[17,22]]
Output:
[null,1,2,2,3]
Explanation:

The first booking alone gives 1. [15,25) overlaps [10,20) on 15..19, so 2. [20,30) touches the first only at 20 (the end is excluded) and overlaps the second, so still 2. Finally [17,22) meets [10,20), [15,25) at 17..19 for 3 at once.

Example 2

Input:
operations = ["PeakBookings","book","book","book","book"]arguments = [[],[0,5],[5,10],[3,7],[4,6]]
Output:
[null,1,1,2,3]
Explanation:

[0,5) and [5,10) are back to back and never overlap, so the peak stays 1. [3,7) overlaps both, but only one at any moment (peak 2). [4,6) joins [0,5) and [3,7) at time 4, giving a peak of 3.

Constraints

  • 0 ≤ start < end ≤ 109
  • At most 105 calls to book
  • The constructor takes no arguments

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.
Time per case
Python 1,000 msC++ 250 msJava 500 msJavaScript 500 msTypeScript 500 ms

Expected complexity

Time
O(log C) per call, C = 10^9
Space
O(q log C)

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.