Driver Free Intervals
MediumIntervals · DoorDash
A delivery platform stores each driver's working shifts and the stretches of time they are already busy with deliveries. Find every period when the driver is on shift and not busy.
All intervals are half-open [start, end): the start is included, the end is not. So [2, 4) and [4, 6) sit back to back with no overlap, and a busy interval that ends exactly when a shift begins (or starts exactly when it ends) does not affect that shift.
Return the free intervals as a list of [start, end) pairs:
- Handle the shifts in the order given. For each shift, list its free intervals in increasing order of start, then move on to the next shift.
- Free intervals never cross a shift boundary. If one busy interval spans two shifts, each shift is trimmed separately.
- Report maximal gaps only. Two free intervals in the same shift must never touch or overlap, so a gap is never split in two.
- Busy intervals come in any order, may overlap or repeat, and may start before a shift or end after it. Two busy intervals that touch (such as
[1, 2)and[2, 3)) leave no gap between them. - If a shift has no free time, it contributes nothing. If nothing is free anywhere, return
[].
The input lists must not be modified.
Example 1
- Input:
- available_driver_intervals(shifts = [[9, 17], [20, 24]], busy = [[14, 16], [10, 12], [11, 13], [22, 23]])
- Output:
- [[9, 10], [13, 14], [16, 17], [20, 22], [23, 24]]
- Explanation
- Busy
[10, 12)and[11, 13)overlap and merge into[10, 13), and the list was not sorted. The first shift keeps[9, 10),[13, 14)and[16, 17); the second keeps[20, 22)and[23, 24).
Example 2
- Input:
- available_driver_intervals(shifts = [[0, 6], [8, 12]], busy = [[4, 9]])
- Output:
- [[0, 4], [9, 12]]
- Explanation
- One busy block covers the end of the first shift and the start of the second. Trimming each shift separately leaves
[0, 4)and[9, 12).
Example 3
- Input:
- available_driver_intervals(shifts = [[3, 7]], busy = [[1, 3], [7, 9]])
- Output:
- [[3, 7]]
- Explanation
- Both busy intervals only touch the shift edges (half-open), so the whole shift
[3, 7)is free.
Constraints
- 0 ≤ shifts.length, busy.length ≤ 105
- Every interval is
[start, end)with-10^9 <= start < end <= 10^9 - Shifts do not overlap one another (they may touch) and may be given in any order
- Busy intervals may be unsorted, overlap, repeat, or extend beyond a shift