The Lamplighters of Dusk Street
The lamplighters' guild has pinned a notice by the inn door.
Dusk Street runs straight from the inn to the river, and every lamp along it must be tended before dark. The guild sends out a fixed number of lamplighters. Each one is given a contiguous stretch of the street, the stretches do not overlap, and together they cover every lamp, in order, with no lamp left out. All of them set off at the same moment, so the street is finished when the slowest lamplighter finishes, and the guild wants that moment to come as early as possible.
Arguments
lamps- a non-empty list of non-negative integers, the minutes each lamp takes to tend, given in street order.crews- an integer, the number of lamplighters, with1 <= crews <=the number of lamps.
Return
Split lamps into exactly crews contiguous, non-empty groups. The cost of a group is the sum of its values. Write lampRounds(lamps, crews), which returns the integer that is the smallest possible value of the largest group cost, over all such splits.
examples
- case 1
lamps of [7, 2, 5, 10, 8], crews of 218 - the best split is [7, 2, 5] costing 14 and [10, 8] costing 18; no split of this list into two stretches has a largest cost below 18 - case 2
lamps of [1, 4, 4], crews of 34 - each lamplighter takes one lamp, and the largest cost is 4 - case 3
lamps of [0, 0, 0, 0, 0], crews of 30 - every split costs nothing - case 4
lamps of [100, 1, 1, 1], crews of 2100 - one lamplighter is stuck with the 100-minute lamp no matter how the street is divided
- reward
- 320 XP
- signature
lampRounds
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- classic two crews
- single lamp, single crew
- one crew takes the whole street
- a crew for every lamp
- all lamps already lit
- one enormous lamp
- ascending street, five crews
- thirty lamps, five crews
- equal lamps split evenly