Compute maximum concurrent trips from intervals
Overview
This question evaluates a candidate's skill in designing efficient algorithms for interval overlap counting, including event ordering, handling half-open interval edge cases, and reasoning about concurrent activity timing.
Uber
Oct 13, 2025, 9:49 PM
Data Scientist
Technical Screen
Coding & Algorithms
0
0
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.