Adeptalgorithms & data structures
The Grave-Hunts of Thrennick Barrows
The barrows of Thrennick stand in a long row on the hillside, and on certain nights their dead walk. The Wardens of Thrennick post a list of grave-hunts: each hunt names the hour a barrow must be entered, the hour it may be left, and the crowns paid to whoever clears it. A lone hunter carries only one hallowed blade, so they may be on at most one hunt at any moment. Any hunt they take, they take whole, from its first hour to its last. They may take hunts in any order the hours allow, and may skip any hunt.
Write bestBounty(hunts).
huntsis a list of hunts. Each hunt is a list of three integers[start, end, reward]with0 <= start < endandreward >= 0. The list is in no particular order, and two hunts may be identical.- A hunt occupies the half-open span of hours from
startup to, but not including,end. Two hunts conflict if their spans share any hour. A hunt ending at hourhdoes not conflict with a hunt starting at hourh. - Return a single integer: the largest total reward a lone hunter can earn by choosing a set of hunts with no two in conflict. If
huntsis empty, return0.
examples
- case 1
hunts [1, 3, 50], [2, 4, 10], [3, 5, 40], [3, 6, 70]120 (take [1, 3, 50] and [3, 6, 70]; the first ends at hour 3, exactly when the second begins) - case 2
hunts [1, 4, 10], [2, 3, 3], [3, 5, 3]10 (the two small hunts fit together for only 6, and both clash with the 10-crown hunt) - case 3
no hunts at all0
- reward
- 320 XP
- signature
bestBounty
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
loading the editor…
- no hunts
- single hunt
- touching hunts both taken
- one big hunt beats two small
- classic choice
- long hunt beats a chain
- unsorted input
- zero reward hunt
- identical spans
- chain beats covering hunt