Maximum Concurrent Bookings After Each Reservation
A reservation service accepts half-open time bookings one at a time. After each new booking it must report the maximum number of bookings that overlap at any instant — the peak concurrency.
Problem
Implement a class that supports book(start, end) for half-open intervals [start, end). After each call, return the largest integer k such that there exist k bookings all overlapping at some single point in time. All bookings are retained.
Input
A sequence of book(start, end) calls with 0 <= start < end.
Output
For each book call, an integer: the current maximum overlap (k-booking) across all bookings made so far.
Constraints
- 0 <= start < end <= 10^9
- At most 400 book calls.
- Half-open intervals: touching endpoints do not overlap.
Examples
Example 1
Input
book(10,20), book(50,60), book(10,40), book(5,15), book(5,10), book(25,55)
Output
1, 1, 2, 3, 3, 3
The third and fourth bookings stack overlaps to 2 then 3 at instants near 10–15.
Example 2
Input
book(24,40), book(40,50)
Output
1, 1
Half-open intervals that touch at 40 do not overlap.