Card 03/ 07
Pattern Choice Example: Finding the Uncovered Hours in a Delivery Roster
Shifts never mention intervals, but each has a start and an end and the question asks for gaps: sort by start and merge.
A problem can call for a pattern without using any of its words, and the cue is then a property of the items: here, a delivery roster whose shifts each have a start and an end, and a question about the time no shift covers, which is the intervals pattern. A depot's drivers work four shifts on the 24-hour clock: 8 to 11, 14 to 18, 10 to 13 and 17 to 20. A shift from 8 to 11 covers 8:00 up to 11:00. The manager wants the hours between the first start and the last end when no driver is on the road.
Which hour has no driver?
13:00 to 14:00. The shifts from 8 to 11 and 10 to 13 cover the morning without a break, and the afternoon pair runs from 14 to 20.
The roster says nothing of intervals, but reading the decision in order finds the sixth branch: each item has a start and an end, and the question asks about gaps. Sorting the shifts by start and merging each one into the last merged stretch when it starts before that stretch ends leaves the covered stretches in order, and the gaps sit between them. The run drew each shift as a bar on one axis of hours, before and after merging, and then the gaps.
before merging
8 10 12 14 16 18 20
8 to 11 ======
14 to 18 ========
10 to 13 ======
17 to 20 ======
after merging
8 10 12 14 16 18 20
8 to 13 ==========
14 to 20 ============
no driver: 13:00 to 14:00
slot per hour: 13:00 (24 slots)Two stretches remain, 8 to 13 and 14 to 20, and the gap between them is the hour with no driver. The last line is a different approach to the same roster: an array with one slot per hour of the day, each shift marking its hours, then a scan for unmarked slots. It finds 13:00 too, because the shifts are whole hours within one day.
| Approach | Cost | Works when |
|---|---|---|
| Sort by start, then merge | O(n log n) time, O(n) for the merged list | Always: its size follows the number of shifts |
| One slot per hour | O(n · h + r) for shifts of h hours over a range of r slots | Times are whole hours over a short range, such as one day |
The slot array fails as soon as the times stop being few and whole: shifts given to the minute over a year need about 525,600 slots, whatever the number of shifts. Merging costs the same for four shifts given to the minute as for four given to the hour, which is why intervals is the pattern to choose and the slot array a shortcut for one day's roster.
← → move through sections and cards