Adeptalgorithms & data structures
The Overlapping Watch
The watch-captain of bitwick keeps the roster for the north wall pinned beside the inn's door. Each entry on the roster is one watcher's shift, written as a pair of integers [start, end]: that watcher stands on the wall from hour start up to but not including hour end. Every pair has start strictly less than end, and shifts may overlap, nest, or repeat freely. The roster is in no particular order.
The captain pays a bonus for the hours when the wall is *well* guarded, and wants that total counted.
Write deepWatch(shifts, k):
shifts— a list of[start, end]pairs of non-negative integers. It may be empty.k— an integer, at least 1.
Return an integer: the number of integer hours h such that at least k of the pairs satisfy start <= h < end.
examples
- case 1
shifts of [[1, 5], [2, 8], [9, 12]], k of 23 (hours 2, 3 and 4 have two watchers each) - case 2
shifts of [[1, 4], [4, 7]], k of 20 (the shifts merely touch; hour 4 belongs only to the second) - case 3
shifts of [[0, 10], [1, 9], [2, 8], [3, 7]], k of 36 (hours 2 through 7 are covered three or more deep)
- reward
- 360 XP
- signature
deepWatch
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
loading the editor…
- two watchers overlap at midwatch
- the union when one watcher suffices
- shifts that only touch
- an empty roster
- more watchers demanded than exist
- nested watches three deep
- a single hour on the wall
- three identical shifts
- the long roster of the winter wall