The Watchfires of the North Wall
A notice pinned by the door of the inn, in the captain's hand:
> The north wall is watched in shifts, and the roster has grown past what I can count by eye. I need to know when the wall is thickest with watchers.
The roster is given as shifts: a list of [start, end] pairs of integers, with start < end in every pair. A watcher assigned the pair [start, end] stands on the wall at every integer hour t with start <= t < end — the end hour itself is not watched.
Write peakWatch(shifts), which returns a list of exactly two integers [count, hour]:
countis the largest number of watchers standing on the wall at any single integer hour.houris the smallest integer hour at which exactly that many watchers stand on the wall.
If shifts is empty, return [0, -1].
Hours may be negative. The same pair may appear more than once, and each occurrence is a separate watcher. The roster is in no particular order.
examples
- case 1
shifts of [[1, 5], [2, 6], [4, 9], [8, 10]][3, 4] — at hour 4 the first three watchers are all on the wall; no hour holds four - case 2
shifts of [[0, 10], [5, 6], [20, 30], [21, 22]][2, 5] — two watchers stand at hour 5 and again at hour 21, and 5 is the earlier - case 3
shifts of [[1, 3], [3, 5]][1, 1] — the first watcher leaves before hour 3, so the shifts never overlap - case 4
shifts of [][0, -1]
- reward
- 320 XP
- signature
peakWatch
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- overlapping roster
- empty roster
- single watcher
- disjoint shifts
- touching ends never overlap
- tie takes the earlier hour
- identical shifts stack
- negative hours
- nested and unsorted