Compute maximum concurrent trips from intervals

Q: Compute maximum concurrent trips from intervals

This is a Coding & Algorithms interview question from Uber for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Compute maximum concurrent trips from intervals

Comments (0)