Wizard Scroll Allocation Strategy
Jane Street● MediumINTERNONSITE INTERVIEWProblem statement
A wizard receives ten scrolls at the start of every day, and unused scrolls persist. On day i, one monster with cost costs[i] appears. The wizard may defeat that monster only on that day by spending its cost.
Return the zero-based days on which the wizard should defeat monsters. Maximize the number defeated, then minimize total scrolls spent, then choose the lexicographically smallest day list.
Function
chooseMonsterDays(costs: int[]) → int[]Examples
Example 1
costs = [5,25,5]return = [0,2]Defeating days 0 and 2 costs ten scrolls total and is feasible; no schedule defeats all three monsters.
Example 2
costs = [10,20,30]return = [0]Only one monster can be defeated. Day 0 has the smallest total spend and therefore wins the tie.
Constraints
1 <= costs.length <= 20.1 <= costs[i] <= 10^4.- A selected schedule is feasible when cumulative spending through every day is at most
10 * (day + 1).