Compute maximum concurrent trips from intervals

You’re given n trip intervals [start, end) in seconds, where start < end, representing when a rider’s trip starts and ends in a city on a specific day. Implement a function that returns (a) the maximum number of concurrent trips at any time, and (b) one time t at which this maximum occurs.

Requirements:

• If one trip ends exactly when another starts (end == start), they do NOT overlap (half-open intervals).
• Time values are integers in [0, 1e9]; n ≤ 1e5.
• Aim for O(n log n) time and O(1) extra space beyond the input (you may reorder in place).
• Return any valid time t achieving the maximum.

Example: Input: [[0,10],[5,12],[11,13],[2,7]] → Output: max = 3, t = 5 (any t in [5,7)).

Follow-ups:

• Also return the smallest time range [L, R) over which the maximum concurrency holds continuously.
• Discuss how your approach changes if the intervals are streaming and you can’t store all of them.

Part 1: Maximum Concurrent Trips and Earliest Time

You are given a list of half-open trip intervals [start, end), where start < end. Return a tuple (max_count, t), where max_count is the maximum number of trips happening at the same time, and t is the earliest integer time at which this maximum occurs. If one trip ends exactly when another starts, they do not overlap. If the input is empty, return (0, None).

Constraints

• 0 <= n <= 10^5
• 0 <= start < end <= 10^9
• Intervals are half-open: [start, end)
• If end == start for two trips, they do not overlap
• An O(n log n) time solution is expected

Examples

Example 1

Input: [[0, 10], [5, 12], [11, 13], [2, 7]]
Output: (3, 5)

Explanation: The maximum overlap is 3, first reached at time 5.

Example 2

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

Explanation: The intervals touch at 3 but do not overlap, so the maximum is 1.

Hints

1. Sort all start times and end times separately, then sweep through them with two pointers.
2. Because the intervals are half-open, when a start time equals an end time, process the end first.

Part 2: Earliest Continuous Range of Maximum Concurrency

You are given a list of half-open trip intervals [start, end), where start < end. Return a tuple (max_count, L, R), where max_count is the maximum number of concurrent trips, and [L, R) is the earliest continuous time range during which the number of active trips equals max_count at every instant. If the maximum occurs on multiple disjoint ranges, return the earliest such range. If the input is empty, return (0, None, None).

Constraints

• 0 <= n <= 10^5
• 0 <= start < end <= 10^9
• Intervals are half-open: [start, end)
• If end == start for two trips, they do not overlap
• An O(n log n) time solution is expected

Examples

Example 1

Input: [[0, 10], [5, 12], [11, 13], [2, 7]]
Output: (3, 5, 7)

Explanation: The concurrency is 3 for the continuous range [5, 7).

Example 2

Input: [[0, 2], [1, 3], [4, 6], [5, 7]]
Output: (2, 1, 2)

Explanation: Maximum concurrency 2 happens on [1, 2) and [5, 6), so return the earliest one.

Hints

1. The active-trip count only changes at interval boundaries, so sweep across sorted unique event times.
2. Aggregate all changes at the same timestamp; if a trip ends and another starts at the same time, the maximum range may continue without a break.

Part 3: Maximum Concurrent Trips in a Start-Sorted Stream

Trips arrive as a stream of half-open intervals [start, end), already sorted by nondecreasing start time. You cannot store all intervals. Process the stream and return a tuple (max_count, t), where max_count is the maximum number of concurrent trips seen so far, and t is the earliest time at which this maximum occurs. If the input is empty, return (0, None). For testing, the stream is provided as a list, but your algorithm should work in one pass using only memory proportional to the number of active trips.

Constraints

• 0 <= n <= 10^5
• 0 <= start < end <= 10^9
• Intervals are half-open: [start, end)
• The input is sorted by nondecreasing start time
• Use only O(k) extra space, where k is the number of active trips

Examples

Example 1

Input: [[0, 10], [2, 7], [5, 12], [11, 13]]
Output: (3, 5)

Explanation: The maximum number of active trips is 3, first reached when the trip starting at 5 arrives.

Example 2

Input: []
Output: (0, None)

Explanation: No trips means no concurrency.

Hints

1. Keep the end times of currently active trips in a min-heap.
2. Before adding a new trip [s, e), remove every active trip with end <= s, because touching intervals do not overlap.