The Nightwatch Roster of Bell Hollow
The watch-captain of Bell Hollow pins her roster to the inn door each week, and she needs to know how much of the night the ridge is *properly* guarded.
A roster is a list of shifts. Each shift is a pair of integers [start, end] with start < end, measured in hours on one continuous timeline (hours may be negative). A shift is on duty during the half-open span from start up to but not including end: it covers an hour t when start <= t < end. The ridge is properly guarded at a moment when at least `k` shifts are on duty at that same moment.
Write guardedHours(shifts, k):
shifts— a list of[start, end]integer pairs, in no particular order. Shifts may overlap, nest, or repeat exactly; the list may be empty.k— an integer, always at least 1.
Return a single integer: the total length of time that is properly guarded, i.e. the summed length of all spans during which at least k shifts are simultaneously on duty. If there is no such span, return 0.
examples
- case 1
shifts of [1,5], [2,8], [6,9]; k of 25 — two watchers are on duty from 2 to 5 and again from 6 to 8 - case 2
shifts of [0,3] and [3,6]; k of 20 — the first ends exactly as the second begins, so they are never both on duty - case 3
shifts of [5,10], [0,3], [2,6], [20,21]; k of 111 — the covered time is 0 to 10, plus 20 to 21
- reward
- 320 XP
- signature
guardedHours
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- three overlapping watches, k of 2
- shifts that merely touch
- k of 1 is the plain union
- empty roster
- k larger than the roster
- identical shifts stack
- nested watches, k of 3
- hours before midnight
- single shift, k of 1