Loading page…
Practice problem · easy
A ride-hailing app keeps each driver's availability as a list of free slots. A slot [start, end) is free from the start minute up to, but not including, the end minute. The slots are sorted, and no two overlap.
The driver now adds a blackout, such as a break or a day off. The app must remove those minutes from the availability. A slot can be cut short, split in two, or removed completely.
Write free_after_blackout(free, blackout).
free is sorted by start, and its slots do not overlap. Each slot has start < end.blackout = [a, b) with a < b.Input: free = [[0, 4], [6, 10], [12, 16], [18, 20]], blackout = [3, 13]
Output: [[0, 3], [13, 16], [18, 20]]Look at each slot in turn. A slot that does not overlap the blackout is kept. A slot that does overlap keeps the part before the blackout, and the part after it, if those parts have minutes.
| Slot | Overlaps [3, 13)? | Result |
|---|---|---|
| [0, 4] | yes | keep [0, 3] before the blackout |
| [6, 10] | yes, fully inside | nothing is left |
| [12, 16] | yes | keep [13, 16] after the blackout |
| [18, 20] | no | keep [18, 20] |
Input: free = [[0, 10]], blackout = [3, 5]
Output: [[0, 3], [5, 10]]The blackout lies inside the slot, so the slot splits into two.
Input: free = [[0, 5]], blackout = [0, 2]
Output: [[2, 5]]The blackout starts with the slot. The part before it has no minutes, so it is left out.
0 ≤ free.length ≤ 100,0000 ≤ start < end ≤ 1,000,000,000 (minutes)0 ≤ a < b ≤ 1,000,000,000Finding an overlapping slot, splitting it and searching again from the start costs up to n × n at n = 100,000. The slots are already sorted, so one pass over them costs only n.
free_after_blackout · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.