‹ back to the board

Sunday, October 4

Adeptalgorithms & data structures

The Gloamwood Hunts of the Ashen Lance

The Ashen Lance, a company of monster-hunters out of Bitwick, has been offered a season's worth of commissions in the Gloamwood: a barrow-hound to run down here, a nest of mire-drakes to burn out there. Each commission names the first and last day of the hunt and the bounty the Margrave will pay for it. The company rides as one band, so it can work only one hunt at a time, and a hunt it takes must be seen through from its first day to its last.

The company's quartermaster wants to know the most silver the Lance can earn this season.

Write bestBounty(hunts).

  • hunts is a list of commissions, each a list of three integers [start, end, bounty], with 1 <= start <= end and bounty >= 1. The company is occupied on every day from start to end, inclusive. The list may be empty and is in no particular order. Two commissions may be identical.
  • The company may take any subset of the commissions, provided no two chosen commissions share a day. Two commissions can both be taken only if one's end is strictly less than the other's start.
  • Return an integer: the largest possible sum of bounties over such a subset. If hunts is empty, return 0.
  • dynamic programming
  • Adept

examples

  1. case 1hunts of [1, 3, 10] and [3, 5, 10]10 - both hunts need day 3, so only one can be taken
  2. case 2hunts of [1, 10, 50], [1, 4, 30] and [5, 10, 30]60 - the two short hunts together beat the single richest one
  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…
  • empty season
  • single hunt
  • shared boundary day clashes
  • adjacent days do not clash
  • greedy by bounty fails
  • one long rich hunt wins
  • mixed overlapping season
  • unsorted input
  • identical one-day hunts
The Gloamwood Hunts of the Ashen Lance · bitwick