The Moonwell Vigils of Selvarin Fen
Deep in Selvarin Fen lies the Moonwell, and the Circle of the Reed Druids keeps watch over it from dusk until dawn, for night-hags come to drink wherever no druid stands guard. The Circle has posted its vigil roll to the board in Bitwick and seeks an adventurer to find every stretch of the night when the well is left unwatched.
Write unwatchedStretches(n, vigils).
nis a non-negative integer: the night runs from minute0to minuten.vigilsis a list of pairs[start, end]of integers with0 <= start < end <= n. A druid on that vigil watches the well from minutestartup to, but not including, minuteend(the half-open span[start, end)).- The pairs may appear in any order. Vigils may overlap, may nest inside one another, may be exact duplicates, and may touch end-to-start. The list may be empty.
Return a list of pairs [start, end] describing every unwatched stretch: the minutes in [0, n) covered by no vigil, grouped into maximal half-open spans [start, end). Each returned pair has start < end, the pairs are sorted by start ascending, and no two returned pairs overlap or touch. If the whole night is watched (or n is 0), return an empty list.
examples
- case 1
n of 100, vigils [[20, 40], [10, 30], [60, 70]][[0, 10], [40, 60], [70, 100]] - case 2
n of 10, vigils [[0, 4], [4, 10]] (one druid hands over to the next at minute 4)[] - the well is never unwatched - case 3
n of 30, vigils [[5, 25], [10, 12], [0, 3], [3, 4]][[4, 5], [25, 30]] - case 4
n of 50, no vigils at all[[0, 50]]
- reward
- 320 XP
- signature
unwatchedStretches
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- overlapping and separate vigils
- touching vigils leave no gap
- no vigils at all
- zero-length night
- nested and unsorted vigils
- single vigil covers the night
- duplicate vigils
- chain of overlaps out of order
- long vigil swallows later short ones