Compute peak concurrent drivers in 24 hours

Given delivery intervals across multiple drivers, compute the maximum number of distinct drivers simultaneously active within the last 24 hours from a query time T. Each delivery is a tuple (driver_id, start_time, end_time) with start_time < end_time; a driver may have multiple intervals. A driver counts as active at a moment if at least one of their intervals covers that moment. Implement peak_concurrent_drivers(T) that returns the maximum number of distinct active drivers in the half-open window [T − 24h, T). Clearly define inclusivity rules (e.g., end exclusive), required data structures, and the algorithm’s time and space complexity. Assume streaming inserts and queries over time.

Compute Peak Concurrent Drivers in 24 Hours

You are given a stream of operations on delivery intervals. Each add operation is a tuple ("add", driver_id, start_time, end_time) and inserts a half-open delivery interval [start_time, end_time) for that driver. Each query operation is a tuple ("query", T) and asks for the maximum number of distinct drivers that are simultaneously active at some moment inside the half-open 24-hour window [T - 24, T). A driver is active at time x if at least one of that driver's inserted intervals contains x. If a driver has multiple overlapping or touching intervals, that driver still counts only once at any moment. Process operations in order: a query only sees adds that appeared earlier in the stream. Return the answer for every query in order.

For an efficient solution, use two layers of data structures: a hash map from driver_id to that driver's merged intervals, and a global range-add/range-max structure over compressed timestamps.

Constraints

• 1 <= len(operations) <= 20000
• For every add operation, start_time < end_time
• -10^9 <= start_time, end_time, T <= 10^9
• driver_id is an integer
• The query window is always the half-open interval [T - 24, T)

Examples

Example 1

Input: ([("add", 1, 0, 10), ("add", 2, 5, 15), ("query", 12)],)
Output: [2]

Explanation: In the window [-12, 12), driver 1 is active on [0, 10) and driver 2 on [5, 12). The peak overlap is 2 on [5, 10).

Example 2

Input: ([("add", 1, 0, 10), ("add", 1, 5, 12), ("add", 2, 6, 8), ("query", 9), ("query", 13)],)
Output: [2, 2]

Explanation: Driver 1's two intervals overlap, so they count as one distinct driver. Driver 2 overlaps driver 1 on [6, 8), making the peak 2 for both queries.

Hints

1. A single driver must never be counted twice at the same time. Maintain each driver's coverage as a sorted list of merged intervals, and when a new interval arrives, only add the parts not already covered by that driver.
2. After coordinate compression, every newly uncovered sub-interval becomes a range +1 update on a segment tree, and every query becomes a range maximum query on [T - 24, T).