Ledger of the Lamplighter's Watch
The lamplighter of bitwick keeps a ledger of lantern shifts for the long road out of town. Each entry records one lantern: the hour it is lit and the hour it is snuffed. The watch-guild pays only for the hours when the road is properly bright, and "properly bright" means a certain number of lanterns burning at once.
You are given shifts, a list of [start, end] pairs of integers, and k, an integer with k >= 1. A shift [start, end] means that lantern burns during every whole hour h with start <= h < end. Every pair satisfies 0 <= start < end. Entries are in no particular order, may overlap in any way, and may repeat exactly.
Write coveredHours(shifts, k), which returns an integer: the number of whole hours h at which at least k of the lanterns are burning.
An empty ledger returns 0. Hours may run into the millions.
examples
- case 1
shifts of [[1,5],[2,7],[6,9]], k of 24 — hours 2, 3 and 4 have two lanterns, and hour 6 has two more - case 2
shifts of [[0,3],[3,6]], k of 20 — the first lantern is already out at hour 3, so no hour has two - case 3
shifts of [[2,5],[2,5],[2,5]], k of 33 — hours 2, 3 and 4
- reward
- 350 XP
- signature
coveredHours
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- three shifts, two lanterns wanted
- shifts that merely touch
- empty ledger
- a single lantern suffices
- more lanterns demanded than exist
- three identical shifts
- nested shifts
- the long night watch