My Calendar III

Hard

You are given a list of bookings where bookings[i] = [start, end] represents a half-open interval [start, end).

Book them one at a time, in order. A k-booking happens when k events have a non-empty intersection. After each booking, record the largest k such that a k-booking exists.

Return the array of those values.

The original problem is a class with a book method called repeatedly. This judge passes the whole call sequence at once and asks for the answer after each call — the same state machine, batched.

Example 1

Input:  bookings = [[10,20],[50,60],[10,40],[5,15],[5,10],[25,55]]
Output: [1,1,2,3,3,3]

Example 2

Input:  bookings = [[1,2],[1,2],[1,2]]
Output: [1,2,3]

Constraints

• 1 <= bookings.length <= 400
• 0 <= start < end <= 10^9