Compute concurrent online drivers

Question

Given each driver’s chronologically sorted delivery records, build an algorithm that, for a timestamp t, returns how many distinct drivers were online at any moment in the previous 24 hours. Optimize using per-driver binary search and justify the complexity.

Count Drivers Online in Last Day

You are given N drivers. For each driver, you are provided a chronologically sorted list of non-overlapping online sessions, each as an inclusive interval [start, end] of integer seconds since epoch. Given a query timestamp t, return how many distinct drivers were online at any moment during the previous 24 hours, defined as the inclusive window [t-86400, t]. A driver counts once if any of their intervals intersects this window.

Constraints

• 0 <= N == len(drivers) <= 200000
• Sum of all intervals across all drivers <= 1000000
• For each driver, intervals are sorted by start ascending and are non-overlapping
• Intervals use inclusive endpoints: start <= end
• Timestamps are integers: -10^15 <= start, end, t <= 10^15
• Return value is in [0, N]

Examples

Example 1

Input: drivers = [[[10,20],[30,40]],[[-100000,-90000]],[[70,80]]], t = 35
Output: 1

Explanation: Window is [-86365, 35]. Only driver 0 overlaps (e.g., [10,20] and [30,40] both intersect). Driver 1's interval ends before the window, driver 2 starts after.

Example 2

Input: drivers = [[[0,10]],[[-86400,-86390]],[[-1,0]],[[50,60]]], t = 0
Output: 3

Explanation: Window is [-86400, 0]. Drivers 0, 1, and 2 intersect the window; driver 3 does not.

Hints

1. A driver is counted if there exists an interval [s,e] with s <= t and e >= t-86400.
2. Because intervals are sorted and non-overlapping, only the last interval with start <= t needs to be checked for overlap with the window.
3. Use binary search per driver to find the rightmost interval whose start <= t, then verify if its end >= t-86400.

Approach

We need to know if a driver has any interval overlapping the inclusive window [t-86400, t]. Since each driver's intervals are sorted by start and non-overlapping, among all intervals with start <= t, only the last such interval can possibly overlap the window; if it does not, earlier intervals end even earlier and cannot overlap. Therefore, for each driver, we binary search for the rightmost interval with start <= t and then check if its end >= t-86400. This yields per-driver O(log k) time, where k is that driver's number of intervals.

• Time complexity: O(D log K_avg), where D is the number of drivers and K_avg is the average number of intervals per driver
• Space complexity: O(1) additional space