Adeptalgorithms & data structures
The Wraith-Patrols of Cardenholt Abbey
The ruined cloister of Cardenholt Abbey is walked by wraiths each night. The Reliquary Guild has sent scouts to record when each wraith walks. The Guild pays a bounty to whoever can name the longest unbroken stretch of the night when the cloister is empty. A thief will need that much time to lift the Abbey's reliquary unseen.
Write longestLull(patrols, night).
nightis a positive integer: the night lasts from minute0up to, but not including, minutenight.patrolsis a list of pairs[start, end]of integers with0 <= start < end <= night. A wraith walks the cloister from minutestartup to, but not including, minuteend.- Patrols may arrive in any order, and they may overlap, nest inside one another, share a start, or touch end-to-start. The list may be empty.
Return an integer: the length of the longest continuous stretch within [0, night) during which no wraith is walking. If some wraith is walking at every moment of the night, return 0.
When one patrol ends at minute t and another begins at minute t, there is no empty stretch between them.
examples
- case 1
patrols [[12,14],[1,3],[2,5],[3,4],[20,25]], night 267. The cloister is watched from 1 to 5, from 12 to 14 and from 20 to 25. The empty stretches are 0–1, 5–12, 14–20 and 25–26, so the longest is 5–12. - case 2
patrols [[0,3],[3,6],[6,10]], night 100. Each patrol begins the minute the last one ends, so the cloister is never empty. - case 3
no patrols at all, night 1010. The whole night is empty.
- reward
- 320 XP
- signature
longestLull
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
loading the editor…
- no patrols leaves whole night
- two separate patrols
- touching patrols leave no gap
- unsorted with nested patrol
- leading gap is longest
- trailing gap after shared start
- single patrol covers night
- unit gaps between patrols
- long patrol swallows later ones