‹ back to the board

Saturday, October 17

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

  • hunts is a list of hunts. Each hunt is a list of three integers [start, end, reward] with 0 <= start < end and reward >= 0. The list is in no particular order, and two hunts may be identical.
  • A hunt occupies the half-open span of hours from start up to, but not including, end. Two hunts conflict if their spans share any hour. A hunt ending at hour h does not conflict with a hunt starting at hour h.
  • 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 hunts is empty, return 0.
  • dynamic programming
  • Adept

examples

  1. case 1hunts [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)
  2. case 2hunts [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)
  3. case 3no hunts at all0
reward
320 XP
signature
bestBounty
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…
  • 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
The Grave-Hunts of Thrennick Barrows · bitwick