Compute unique-dasher concurrency with tie-breaking
Company: Rippling
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given N delivery assignments, each as (dasherId, startTime, endTime) with 0 <= startTime < endTime. A single dasher may hold multiple overlapping orders. Design an algorithm to compute:
(
1) the maximum number of simultaneously active dashers at any moment (count each dasher at most once at any instant), and
(
2) one timestamp (or interval) when this maximum occurs. Use an event-sweep approach: specify the event format, how you avoid double-counting when the same dasher has multiple overlapping orders (e.g., maintain a per-dasher active-order counter that changes the global active-dasher count only on 0->1 and 1->0 transitions), and your tie-breaking policy when multiple events share the same timestamp (process end (-
1) before start (+
1)). In Python, show a correct sort key that enforces these rules (e.g., key=(time, delta, dasherId) with delta in {-1,+1}) and explain why putting dasherId before delta can break correctness. Analyze time and space complexity.
Quick Answer: The question evaluates understanding of sweep-line/event-sweep algorithms, interval overlap handling, tie-breaking and stable sort ordering as they affect deduplicating concurrent entities, situated in the Coding & Algorithms domain.
You are given a list of delivery assignments. Each assignment is a tuple `(dasherId, startTime, endTime)` with `0 <= startTime < endTime`. An assignment is active on the half-open interval `[startTime, endTime)`.
A single dasher may hold multiple overlapping orders, but at any instant that dasher must be counted at most once.
Write a function `solution(assignments)` that returns a list `[maxDashers, left, right]` where:
- `maxDashers` is the maximum number of distinct dashers active at the same time.
- `[left, right)` is the earliest interval between consecutive event times where this maximum occurs.
- If `assignments` is empty, return `[0, -1, -1]`.
Expected approach: use an event sweep.
- Represent each order as two events `(time, delta, dasherId)`.
- Use `delta = +1` for a start event and `delta = -1` for an end event.
- Maintain a per-dasher active-order counter. The global active-dasher total changes only when a dasher transitions from `0 -> 1` active orders or from `1 -> 0` active orders.
- When multiple events share the same timestamp, process all end events before start events. In Python, a correct sort key is `key=lambda e: (e[0], e[1], e[2])` because `-1 < +1`.
- A key like `(time, dasherId, delta)` can break correctness because it may process a start at time `t` before an end at time `t` just because the start has a smaller `dasherId`, violating the required end-before-start tie rule.
Important: process all events at the same timestamp before evaluating the interval to the next timestamp.
Constraints
- 0 <= N <= 2 * 10^5, where N is the number of assignments
- 0 <= startTime < endTime <= 10^9
- dasherId is an integer
- The assignments are not necessarily sorted
Examples
Input: []
Expected Output: [0, -1, -1]
Explanation: There are no assignments, so the maximum number of active dashers is 0 and no interval exists.
Input: [(1, 1, 5), (1, 2, 6), (2, 3, 4)]
Expected Output: [2, 3, 4]
Explanation: Dasher 1 has overlapping orders but still counts only once. On [3, 4), dashers 1 and 2 are both active, so the maximum distinct count is 2.
Hints
- Turn every assignment into two sweep events. What event ordering guarantees that an order ending at time t is removed before an order starting at time t is added?
- Because the same dasher can have overlapping orders, keep a hash map from dasherId to its active-order count. Only change the distinct-dasher total when that count moves between 0 and 1.