‹ back to the board

Monday, October 5

Adeptalgorithms & data structures

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).

  • n is a non-negative integer: the night runs from minute 0 to minute n.
  • vigils is a list of pairs [start, end] of integers with 0 <= start < end <= n. A druid on that vigil watches the well from minute start up to, but not including, minute end (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.

  • interval merging
  • Adept

examples

  1. case 1n of 100, vigils [[20, 40], [10, 30], [60, 70]][[0, 10], [40, 60], [70, 100]]
  2. case 2n of 10, vigils [[0, 4], [4, 10]] (one druid hands over to the next at minute 4)[] - the well is never unwatched
  3. case 3n of 30, vigils [[5, 25], [10, 12], [0, 3], [3, 4]][[4, 5], [25, 30]]
  4. case 4n of 50, no vigils at all[[0, 50]]
reward
320 XP
signature
unwatchedStretches
not yet run

TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.

loading the editor…
  • 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
The Moonwell Vigils of Selvarin Fen · bitwick