Katkat
Back

Compute maximum concurrent trips from intervals

UberData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

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.

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.