Compute maximum simultaneous drivers
Company: Rippling
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: This English summary evaluates the candidate's proficiency in algorithm design and complexity analysis within the Coding & Algorithms domain, specifically for aggregating interval data and computing concurrent counts.
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
Input: ([],)
Expected Output: 0
Explanation: There are no intervals, so no drivers are ever online.
Input: ([[5, 10]],)
Expected Output: 1
Explanation: A single non-empty interval means exactly one driver is online from time 5 up to, but not including, 10.
Input: ([[1, 3], [3, 5], [5, 8]],)
Expected Output: 1
Explanation: Because intervals are half-open, each interval ends exactly when the next begins, so they never overlap.
Input: ([[1, 4], [1, 4], [1, 4], [2, 2]],)
Expected Output: 3
Explanation: The zero-length interval [2, 2) contributes nothing. The other three identical intervals overlap completely, so the maximum is 3.
Input: ([[-2, 2], [-1, 3], [0, 0], [2, 5], [2, 6], [3, 4]],)
Expected Output: 3
Explanation: The zero-length interval [0, 0) contributes nothing. The maximum number of simultaneous drivers is 3, achieved on [2, 3) and again on [3, 4).
Input: ([[1, 5], [2, 5], [5, 7], [5, 8], [5, 5]],)
Expected Output: 2
Explanation: At time 5, the first two intervals end and the next two begin. Since end_time is excluded, the count remains 2, and [5, 5) contributes nothing.
Solution
def solution(intervals):
from collections import defaultdict
delta = defaultdict(int)
for start, end in intervals:
if start >= end:
continue
delta[start] += 1
delta[end] -= 1
current = 0
best = 0
for time in sorted(delta):
current += delta[time]
if current > best:
best = current
return best
Time complexity: O(N log N). Space complexity: O(N).
Hints
- Convert each interval into two events: +1 when a driver comes online and -1 when a driver goes offline.
- 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.