Compute maximum simultaneous drivers

Given N driver online intervals [start_time, end_time) during a day, compute the maximum number of drivers simultaneously online at any moment. Handle large N, overlapping intervals, and identical timestamps. Describe and implement an efficient algorithm, analyze time and space complexity, and discuss how to support streaming updates where intervals arrive incrementally and may be corrected.

Compute Maximum Simultaneous Drivers

Given N half-open driver online intervals [start_time, end_time) during a day, return the maximum number of drivers who are online at the same moment. Intervals may overlap heavily, multiple intervals may share identical timestamps, and N can be large, so an O(N^2) approach is too slow.

Important details:

• A driver is online at start_time.
• A driver is not online at end_time.
• Zero-length intervals [t, t) contribute nothing.

For the coding task, implement the efficient batch algorithm. As a follow-up discussion, explain how you would support streaming interval inserts, deletes, or corrections as data arrives incrementally.

Constraints

• 0 <= N <= 200000
• -10^9 <= start_time <= end_time <= 10^9
• Intervals are half-open: [start_time, end_time)
• Many intervals may share the same start or end timestamp

Examples

Example 1

Input: ([],)
Output: 0

Explanation: There are no intervals, so no drivers are ever online.

Example 2

Input: ([[5, 10]],)
Output: 1

Explanation: A single non-empty interval means exactly one driver is online from time 5 up to, but not including, 10.

Hints

1. Convert each interval into two events: +1 when a driver comes online and -1 when a driver goes offline.
2. Because intervals are [start, end), drivers ending at time t should not be counted at t. Aggregating all changes by timestamp and sweeping in sorted order handles identical timestamps correctly.